Submission #389631

#TimeUsernameProblemLanguageResultExecution timeMemory
389631i_am_noobPermutation Recovery (info1cup17_permutation)C++17
10 / 100
13 ms15192 KiB
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx2") #define ll long long //#define int ll #define rep(n) rep1(i,n) #define rep1(i,n) rep2(i,0,n) #define rep2(i,a,b) for(int i=a; i<(b); ++i) #define rep3(i,a,b) for(int i=a; i>=(b); --i) #define pb push_back #define pii pair<int,int> #define sz(a) ((int)a.size()) #define all(a) a.begin(),a.end() #define pow2(x) (1ll<<(x)) #define inf 0x3f3f3f3f3f3f3f3f #ifdef i_am_noob #define bug(...) cerr << "#" << __LINE__ << " " << #__VA_ARGS__ << "- ", _do(__VA_ARGS__) template<typename T> void _do(T x){cerr << x << endl;} template<typename T, typename ...S> void _do(T x, S... y){cerr << x << ", ";_do(y...);} #else #define bug(...) 49 #endif const int maxn=70005,mod=1000000007; #define num vector<int> int n,val[maxn*4],minid[maxn*4],ans[maxn]; num a[maxn],minn[maxn*4],tag[maxn*4]; void noob(num& x){ if(x.empty()){ x.pb(0); return; } rep(sz(x)-1){ while(x[i]>=100000000) x[i]-=100000000,x[i]++; while(x[i]<0) x[i]+=100000000,x[i+1]--; } while(x.back()>=100000000||x.back()<=-100000000){ x.pb(x.back()/100000000); x[sz(x)-2]%=100000000; } while(sz(x)>1&&x.back()==0) x.pop_back(); } void ri(num& x){ x.clear(); string str; cin >> str; reverse(all(str)); while(sz(str)%8) str+='0'; for(int i=0; i<sz(str); i+=8){ x.pb(0); rep3(j,i+7,i) x.back()=x.back()*10+(str[j]^'0'); } } num operator +(const num& x, const num& y){ int k=max(sz(x),sz(y)); num res(k); rep(sz(x)) res[i]+=x[i]; rep(sz(y)) res[i]+=y[i]; noob(res); return res; } num operator -(const num& x, const num& y){ int k=max(sz(x),sz(y)); num res(k); rep(sz(x)) res[i]+=x[i]; rep(sz(y)) res[i]-=y[i]; noob(res); return res; } num operator +=(num& x, const num& y){ int k=max(sz(x),sz(y)); x.resize(k); rep(sz(y)) x[i]+=y[i]; noob(x); return x; } bool operator <(const num& x, const num& y){ if(x.back()<0&&y.back()>=0) return true; if(y.back()<0&&x.back()>=0) return false; bool flag=0; if(x.back()<0) flag=1; if(sz(x)<sz(y)) return 1^flag; if(sz(y)<sz(x)) return flag; rep3(i,sz(x)-1,0){ if(x[i]<y[i]) return true; if(x[i]>y[i]) return false; } return false; } void pull(int k){ val[k]=val[k<<1]+val[k<<1|1]; if(!val[k<<1]) return minn[k]=minn[k<<1|1],minid[k]=minid[k<<1|1],void(); if(!val[k<<1|1]) return minn[k]=minn[k<<1],minid[k]=minid[k<<1],void(); if(minn[k<<1]<minn[k<<1|1]) minn[k]=minn[k<<1],minid[k]=minid[k<<1]; else minn[k]=minn[k<<1|1],minid[k]=minid[k<<1|1]; } void push(int k, int l, int r){ if(l!=r){ minn[k<<1]+=tag[k]; minn[k<<1|1]+=tag[k]; tag[k<<1]+=tag[k]; tag[k<<1|1]+=tag[k]; } tag[k]=num(1); } void build(int k, int l, int r){ if(l==r){ minn[k]=a[l]; minid[k]=l; val[k]=1; return; } int mid=l+r>>1; build(k<<1,l,mid),build(k<<1|1,mid+1,r); pull(k); } void modify(int k, int l, int r, int ql, int qr, num& x){ if(l>qr||r<ql) return; if(ql<=l&&qr>=r){ minn[k]+=x,tag[k]+=x; return; } int mid=l+r>>1; push(k,l,r); modify(k<<1,l,mid,ql,qr,x),modify(k<<1|1,mid+1,r,ql,qr,x); pull(k); } void modify2(int k, int l, int r, int p){ if(l==r){ val[k]--; return; } int mid=l+r>>1; push(k,l,r); if(p<=mid) modify2(k<<1,l,mid,p); else modify2(k<<1|1,mid+1,r,p); pull(k); } void print(int k, int l, int r){ bug(k,l,r,minid[k]); for(auto i: minn[k]) bug(i); if(l==r) return; push(k,l,r); int mid=l+r>>1; print(k<<1,l,mid),print(k<<1|1,mid+1,r); } signed main(){ ios_base::sync_with_stdio(0),cin.tie(0); cin >> n; rep(n) ri(a[i]); rep(n) for(auto j: a[i]) bug(i,j); rep3(i,n-1,1) a[i]=a[i]-a[i-1]; rep(n) for(auto j: a[i]) bug(i,j); build(1,0,n-1); rep(n){ int x=minid[1]; ans[x]=i+1; bug(x); modify2(1,0,n-1,x); num tmp(1); tmp=tmp-a[x]; modify(1,0,n-1,x+1,n-1,tmp); } rep(n) cout << ans[i] << ' '; cout << "\n"; }

Compilation message (stderr)

permutation.cpp: In function 'void build(int, int, int)':
permutation.cpp:126:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  126 |     int mid=l+r>>1;
      |             ~^~
permutation.cpp: In function 'void modify(int, int, int, int, int, std::vector<int>&)':
permutation.cpp:137:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  137 |     int mid=l+r>>1;
      |             ~^~
permutation.cpp: In function 'void modify2(int, int, int, int)':
permutation.cpp:148:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  148 |     int mid=l+r>>1;
      |             ~^~
permutation.cpp: In function 'void print(int, int, int)':
permutation.cpp:24:18: warning: statement has no effect [-Wunused-value]
   24 | #define bug(...) 49
      |                  ^~
permutation.cpp:156:5: note: in expansion of macro 'bug'
  156 |     bug(k,l,r,minid[k]);
      |     ^~~
permutation.cpp:24:18: warning: statement has no effect [-Wunused-value]
   24 | #define bug(...) 49
      |                  ^~
permutation.cpp:157:26: note: in expansion of macro 'bug'
  157 |     for(auto i: minn[k]) bug(i);
      |                          ^~~
permutation.cpp:157:14: warning: unused variable 'i' [-Wunused-variable]
  157 |     for(auto i: minn[k]) bug(i);
      |              ^
permutation.cpp:160:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  160 |     int mid=l+r>>1;
      |             ~^~
permutation.cpp: In function 'int main()':
permutation.cpp:24:18: warning: statement has no effect [-Wunused-value]
   24 | #define bug(...) 49
      |                  ^~
permutation.cpp:168:30: note: in expansion of macro 'bug'
  168 |     rep(n) for(auto j: a[i]) bug(i,j);
      |                              ^~~
permutation.cpp:168:21: warning: unused variable 'j' [-Wunused-variable]
  168 |     rep(n) for(auto j: a[i]) bug(i,j);
      |                     ^
permutation.cpp:24:18: warning: statement has no effect [-Wunused-value]
   24 | #define bug(...) 49
      |                  ^~
permutation.cpp:170:30: note: in expansion of macro 'bug'
  170 |     rep(n) for(auto j: a[i]) bug(i,j);
      |                              ^~~
permutation.cpp:170:21: warning: unused variable 'j' [-Wunused-variable]
  170 |     rep(n) for(auto j: a[i]) bug(i,j);
      |                     ^
permutation.cpp:24:18: warning: statement has no effect [-Wunused-value]
   24 | #define bug(...) 49
      |                  ^~
permutation.cpp:175:9: note: in expansion of macro 'bug'
  175 |         bug(x);
      |         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...