You are viewing a single comment's thread. Return to all comments →
java code:
#include <bits/stdc++.h> #define pb push_back #define sqr(x) (x)*(x) #define sz(a) int(a.size()) #define reset(a,b) memset(a,b,sizeof(a)) #define oo 1000000007 using namespace std; typedef pair<int,int> pii; typedef long long ll; char l[1000007],r[1000007]; int m,n; void plus1(int pos){ int t=1; for(int i=pos; i>=1; --i){ if(l[i]=='9') l[i]='0'; else{ ++l[i]; break; } } } vector<int> sub9(int s, int f){ int t=0; vector<int> ans; for(int i=f; i>=s; --i){ int v='0'-l[i]-t; if(v<0){ v+=10; t=1; }else{ t=0; } ans.pb(v); } return ans; } vector<int> sub(int s, int f){ int t=0; vector<int> ans; for(int i=f; i>=s; --i){ int v=r[i]-l[i]-t; if(v<0){ v+=10; t=1; }else{ t=0; } ans.pb(v); } return ans; } vector<int> add(vector<int> &a, vector<int> &b){ while(sz(a)<sz(b)) a.pb(0); while(sz(b)<sz(a)) b.pb(0); vector<int> c; int t=0; for(int i=0; i<sz(a); ++i){ int v=a[i]+b[i]+t; c.pb(v%10); t=v/10; } if(t>0) c.pb(t); return c; } void printVector(vector<int> &a){ for(int i=sz(a)-1; i>=0; --i) printf("%d",a[i]); } struct Block{ int s; vector<int> cnt; Block(){} Block(int _s, vector<int> &_cnt){ s = _s; cnt = _cnt; while(sz(cnt)>1 && cnt[sz(cnt)-1]==0) cnt.pop_back(); } }; vector<Block> result; int main(){ // freopen("input.txt","r",stdin); scanf("%s",l+1); m=strlen(l+1); scanf("%s",r+1); n=strlen(r+1); for(int i=n; i>=n-m+1; --i) l[i]=l[i-(n-m)]; for(int i=n-m; i>=1; --i) l[i]='0'; int x=0; while(x<=n && l[x+1]==r[x+1]) ++x; if(x>n){ puts("1"); puts("0 1"); return 0; } while(x<n){ if(x==n-1){ vector<int> cnt; cnt.pb(r[n]-l[n]+1); result.pb(Block(0,cnt)); l[n]=r[n]; break; }else if(l[n]!='1'){ vector<int> cnt; cnt.pb(0); while(l[n]!='1'){ plus1(n); ++cnt[0]; while(x<n && l[x+1]==r[x+1]) ++x; if(x==n){ ++cnt[0]; break; } } result.pb(Block(0,cnt)); }else{ int u=n-1; while(u-1>x && l[u]=='0') --u; int len=n-u; int s=1; while((1<<(s)) <= len) ++s; int leftBound = n - (1<<(s)); int rightBound = n - (1<<(s-1)); leftBound = max(leftBound,0); if(x < leftBound){ vector<int> cnt = sub9(leftBound+1,rightBound); result.pb(Block(s, cnt)); for(int i=leftBound+1; i<=rightBound; ++i) l[i]='0'; l[n]='0'; plus1(leftBound); }else{ vector<int> cnt = sub(leftBound+1, rightBound); result.pb(Block(s, cnt)); for(int i=leftBound+1; i<=rightBound; ++i) l[i]=r[i]; l[n]='0'; } while(x<n && l[x+1]==r[x+1]) ++x; if(x<n) l[n]='1'; } } printf("%d\n",sz(result)); for(int i=0; i<sz(result); ){ int j=i; vector<int> sum = result[i].cnt; while(j+1<sz(result) && result[j+1].s==result[i].s){ vector<int> t=add(sum, result[++j].cnt); sum = t; } printf("%d ",result[i].s); printVector(sum); i=j+1; puts(""); } }
Seems like cookies are disabled on this browser, please enable them to open this website
Square-Ten Tree
You are viewing a single comment's thread. Return to all comments →
java code: