Submission #636489

#TimeUsernameProblemLanguageResultExecution timeMemory
636489Dec0DeddPermutation Recovery (info1cup17_permutation)C++14
100 / 100
3994 ms163472 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int base = 1000000000; const int base_digits = 9; struct bigint { vector<int> a; int sign; /*<arpa>*/ int size(){ if(a.empty())return 0; int ans=(a.size()-1)*base_digits; int ca=a.back(); while(ca) ans++,ca/=10; return ans; } /*</arpa>*/ bigint() : sign(1) { } bigint(long long v) { *this = v; } bigint(const string &s) { read(); } void operator=(const bigint &v) { sign = v.sign; a = v.a; } void operator=(long long v) { sign = 1; a.clear(); if (v < 0) sign = -1, v = -v; for (; v > 0; v = v / base) a.push_back(v % base); } bigint operator+(const bigint &v) const { if (sign == v.sign) { bigint res = v; for (int i = 0, carry = 0; i < (int) max(a.size(), v.a.size()) || carry; ++i) { if (i == (int) res.a.size()) res.a.push_back(0); res.a[i] += carry + (i < (int) a.size() ? a[i] : 0); carry = res.a[i] >= base; if (carry) res.a[i] -= base; } return res; } return *this - (-v); } bigint operator-(const bigint &v) const { if (sign == v.sign) { if (abs() >= v.abs()) { bigint res = *this; for (int i = 0, carry = 0; i < (int) v.a.size() || carry; ++i) { res.a[i] -= carry + (i < (int) v.a.size() ? v.a[i] : 0); carry = res.a[i] < 0; if (carry) res.a[i] += base; } res.trim(); return res; } return -(v - *this); } return *this + (-v); } void operator*=(int v) { if (v < 0) sign = -sign, v = -v; for (int i = 0, carry = 0; i < (int) a.size() || carry; ++i) { if (i == (int) a.size()) a.push_back(0); long long cur = a[i] * (long long) v + carry; carry = (int) (cur / base); a[i] = (int) (cur % base); //asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base)); } trim(); } void operator+=(const bigint &v) { *this = *this + v; } void operator-=(const bigint &v) { *this = *this - v; } bool operator<(const bigint &v) const { if (sign != v.sign) return sign < v.sign; if (a.size() != v.a.size()) return a.size() * sign < v.a.size() * v.sign; for (int i = a.size() - 1; i >= 0; i--) if (a[i] != v.a[i]) return a[i] * sign < v.a[i] * sign; return false; } bool operator>(const bigint &v) const { return v < *this; } bool operator<=(const bigint &v) const { return !(v < *this); } bool operator>=(const bigint &v) const { return !(*this < v); } bool operator==(const bigint &v) const { return !(*this < v) && !(v < *this); } bool operator!=(const bigint &v) const { return *this < v || v < *this; } void trim() { while (!a.empty() && !a.back()) a.pop_back(); if (a.empty()) sign = 1; } bool isZero() const { return a.empty() || (a.size() == 1 && !a[0]); } bigint operator-() const { bigint res = *this; res.sign = -sign; return res; } bigint abs() const { bigint res = *this; res.sign *= res.sign; return res; } void read() { string s; cin>>s; sign = 1; a.clear(); int pos = 0; while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) { if (s[pos] == '-') sign = -sign; ++pos; } for (int i = s.size() - 1; i >= pos; i -= base_digits) { int x = 0; for (int j = max(pos, i - base_digits + 1); j <= i; j++) x = x * 10 + s[j] - '0'; a.push_back(x); } trim(); } }; #define ll long long #define pii pair<bigint, int> const int N = 7e4+1; ll ans[N]; pii T[4*N]; bigint L[4*N], a[N]; bigint zero; bigint mn=-1; void push(int v) { T[2*v].first+=L[v], T[2*v+1].first+=L[v]; L[2*v]+=L[v], L[2*v+1]+=L[v]; L[v]=zero; } int comb(int v) { int a=2*v, b=2*v+1; if (T[a].first == T[b].first) { if (T[a].second > T[b].second) return a; return b; } if (T[a].first == 0) return a; if (T[b].first == 0) return b; if (T[a].first < 0) return b; if (T[b].first < 0) return a; if (T[a].first < T[b].first) return a; return b; } void upd(int v, int l, int r, int ql, int qr, bigint val) { if (l > qr || r < ql) return; if (l >= ql && r <= qr) { T[v].first-=val, L[v]-=val; if (l < r) push(v); return; } int m=(l+r)/2; push(v); upd(2*v, l, m, ql, qr, val), upd(2*v+1, m+1, r, ql, qr, val); T[v]=T[comb(v)]; } void rem(int v, int l, int r, int p) { if (l == r) { T[v]={mn, l}; return; } int m=(l+r)/2; push(v); if (p <= m) rem(2*v, l, m, p); else rem(2*v+1, m+1, r, p); T[v]=T[comb(v)]; } void build(int v, int l, int r) { if (l == r) { T[v]={a[l], l}; return; } int m=(l+r)/2; build(2*v, l, m), build(2*v+1, m+1, r); T[v]=T[comb(v)]; } int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int n; cin>>n; bigint lst; lst.read(); a[1]=lst-1; for (int i=2; i<=n; ++i) { bigint x; x.read(); bigint nv=x-lst; lst=x; a[i]=nv-1; } build(1, 1, n); for (int i=1; i<=n; ++i) { int x=T[1].second; rem(1, 1, n, x), upd(1, 1, n, x, n, a[x]+1); ans[x]=i; } for (int i=1; i<=n; ++i) cout<<ans[i]<<" "; cout<<"\n"; }
#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...