Submission #389523

#TimeUsernameProblemLanguageResultExecution timeMemory
389523balbitPermutation Recovery (info1cup17_permutation)C++14
100 / 100
3634 ms401448 KiB
#include <bits/stdc++.h> #undef BALBIT #pragma GCC optimize("Ofast", "unroll-loops") //#ifndef BALBIT //#include "grader.h" //#endif using namespace std; #define ll long long #define pii pair<int, int> #define f first #define s second #define REP(i,n) for (int i = 0; i<n; ++i) #define REP1(i,n) for (int i = 1; i<=n; ++i) #define SZ(x) (int)((x).size()) #define ALL(x) (x).begin(), (x).end() #define pb push_back #ifdef BALBIT #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(...) #define endl '\n' #endif // BALBITs #define LL __int128 const int maxn = 7e4+5; struct big{ vector<ll> ho; // static const ll bits = 62; static const ll cap = 1000000000000000000ll; // each digit stores [0,cap] void mul(int x) { // bug("mul in "); ll over = 0; REP(i, SZ(ho)) { LL tmp = ho[i] * (LL)x + over; over = tmp/cap; ho[i] = tmp % cap; } if (over) { ho.pb(over); } while (SZ(ho) && ho.back() == 0) ho.pop_back(); // bug("mul out"); } void add(int x) { ll over = x; REP(i, SZ(ho)) { ll tmp = ho[i] + over; over = tmp / cap; ho[i] = tmp % cap; if (over == 0) break; } if (over) { ho.pb(over); } while (SZ(ho) && ho.back() == 0) ho.pop_back(); } void add(big &x) { while (SZ(ho) < SZ(x.ho)) ho.pb(0); // while (SZ(ho) > SZ(x.ho)) x.ho.pb(0); ll over = 0; REP(i, SZ(ho)) { ll tmp = ho[i] + (i<SZ(x.ho)?x.ho[i]:0) + over; over = tmp / cap; ho[i] = tmp % cap; if (over == 0 && i+1>=SZ(x.ho)) break; } if (over) { ho.pb(over); } while (SZ(ho) && ho.back() == 0) ho.pop_back(); } void sub(big &x) { while (SZ(ho) < SZ(x.ho)) ho.pb(0); // while (SZ(ho) > SZ(x.ho)) x.ho.pb(0); ll over = 0; REP(i, SZ(ho)) { ll tmp = ho[i] - (i < SZ(x.ho)?x.ho[i]:0) - over; over = 0; while (tmp < 0) { tmp += cap; over++; } ho[i] = tmp; if (over == 0 && i+1>=SZ(x.ho)) break; } if (over) { bug("negative number oof"); // while (1); } while (SZ(ho) && ho.back() == 0) ho.pop_back(); } bool operator == (big &x) { if (SZ(ho) != SZ(x.ho)) return 0; return x.ho == ho; } bool operator < (big &x) { if (SZ(x.ho) > SZ(ho)) { return 1; } if (SZ(ho) > SZ(x.ho)) { return 0; } for (int i = SZ(ho)-1; i>=0; --i) { if (ho[i] != x.ho[i]) { if (ho[i] < x.ho[i]) return 1; if (ho[i] > x.ho[i]) return 0; } } return 0; } int operator ^ (big &x) { if (SZ(x.ho) > SZ(ho)) { return 1; } if (SZ(ho) > SZ(x.ho)) { return -1; } for (int i = SZ(ho)-1; i>=0; --i) { if (ho[i] != x.ho[i]) { if (ho[i] < x.ho[i]) return 1; if (ho[i] > x.ho[i]) return -1; } } return 0; } big(string s) { ll nw = 0; ll p10 = 1; for (int i = SZ(s)-1; i>=0; --i) { nw += p10 * (s[i]-'0'); p10 *= 10; if (p10 == cap) { p10 = 1; ho.pb(nw); nw = 0; } } if (nw) { ho.pb(nw); } } big(){} }; pair<big, int> s [maxn*4]; big tg[maxn*4]; //bool neg[maxn*4]; int ans[maxn]; int n; bool Ra(pair<big, int> &a, pair<big, int> &b) { // is a better than b? if (a.s == -1) return 0; if (b.s == -1) return 1; int y = a.f^b.f; return y==0? a.s > b.s : y==1; } void push(int o, int l, int r) { if (s[o].s == -1) return; if (tg[o].ho.empty()) return; s[o].f.sub(tg[o]); if (l!=r) { tg[o*2].add(tg[o]); tg[o*2+1].add(tg[o]); } tg[o].ho.clear(); } big in[maxn], a[maxn], org[maxn]; void build(int o=1, int l=0, int r=n-1) { if (l == r) { s[o] = {org[l], l}; return; } int mid = (l+r)/2; build(o*2,l,mid); build(o*2+1,mid+1,r); if (Ra(s[o*2], s[o*2+1])) { s[o] = s[o*2]; }else{ s[o] = s[o*2+1]; } } void MO(int L, int R, big &v, bool sub, int o=1, int l=0, int r = n-1) { if (s[o].s == -1) return; push(o,l,r); if (l >= L && r <= R) { if (v.ho.empty()) return; s[o].f.sub(v); if (l!=r) { tg[o*2].add(v); tg[o*2+1].add(v); } return; } if (l > R || r < L) return; int mid = (l+r)/2; MO(L,R,v,sub,o*2,l,mid); MO(L,R,v,sub,o*2+1,mid+1,r); if (Ra(s[o*2], s[o*2+1])) { s[o] = s[o*2]; }else{ s[o] = s[o*2+1]; } } big INF; void MO2(int p, int o=1, int l=0, int r = n-1) { push(o,l,r); if (l > p || r < p) return; if (l == r) { s[o] = {INF, -1}; return; } int mid = (l+r)/2; MO2(p,o*2,l,mid); MO2(p,o*2+1,mid+1,r); if (Ra(s[o*2], s[o*2+1])) { s[o] = s[o*2]; }else{ s[o] = s[o*2+1]; } } signed main(){ ios::sync_with_stdio(0), cin.tie(0); // freopen("out.txt", "r", stdin); // freopen("in.txt", "r", stdin); // clock_t ts =clock(); { char c = ' '; while (!(c>='0' && c<='9')) c = getchar(); while (c>='0' && c<='9') { n = (n*10) + (c-'0'); c = getchar(); } } big ps("1"); string bigstring; REP(i, 0) bigstring.pb('9'); INF = big(bigstring); REP(i,n) { string s; char c = ' '; while (!(c>='0' && c<='9')) c = getchar(); while (c>='0' && c<='9') { s.pb(c); c=getchar(); } in[i] = a[i] = big(s); if (i) a[i].sub(in[i-1]); org[i] = ps; org[i].sub(a[i]); bug(org[i].ho.size()==0?0:org[i].ho[0]); bug(a[i].ho.size()==0?0:a[i].ho[0]); ps.add(a[i]); // if (i % 10 == 0) cout<<i<<endl<<flush; } // cout<<((clock() - ts) / (double)CLOCKS_PER_SEC)<<endl; // return 0; // cout<<org[n-1].ho[0]<<endl; // return 0; build(); // bug(s[1].s); for (int i = n; i>=1; i--) { pair<big, int> &hi = s[1]; int v = hi.s; // bug(v+1, a[v].ho[0]); ans[v]=i; MO(v+1, n-1, a[v],1); MO2(v); } REP(i,n) cout<<ans[i]<<' '; cout<<endl; }
#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...