Submission #389576

#TimeUsernameProblemLanguageResultExecution timeMemory
389576Kevin_Zhang_TWPermutation Recovery (info1cup17_permutation)C++17
78 / 100
1813 ms156188 KiB
#pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; using ll = long long; #define pb emplace_back #define AI(i) begin(i), end(i) template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); } template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); } #ifdef KEV #define DE(args...) kout("[ " + string(#args) + " ] = ", args) void kout() { cerr << endl; } template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); } template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; } #else #define DE(...) 0 #define debug(...) 0 #endif unsigned mrand() { static unsigned x = 12323421; return (++x) *= 0xdefaced; } const ll MAX_N = 100000, BD = 1e18, WID = 18, MAX_D = 30; template<class T> struct mvec { T a[MAX_D]; int sz = 0; int size() { return sz; } void pop_back() { --sz; } T &back() { return a[sz-1]; } T& operator[](int ind) { return a[ind]; } void pb(T v) { a[sz++] = v; } mvec(int n) { sz = n; for (int i = 0;i < sz;++i) a[i] = 0; } mvec(ll n) { sz = n; for (int i = 0;i < sz;++i) a[i] = 0; } mvec () {} void resize(int v) { if (sz > v) sz = 0; else while (sz < v) pb(0); } }; #define vector mvec struct mint { vector<ll> val; mint(string s = "0") { ll len = 0, v = 0, sc = 1; reverse(AI(s)); for (int i = 0;i < s.size();++i) { v += sc * (s[i] - '0'); if (++len == WID) { val.pb(v); v = len = 0, sc = 1; } if (len) sc *= 10; } val.pb(v); } mint(vector<ll> v) : val(v) { upd(); } mint(ll v) { val.pb(v); upd(); } void shrink() { while (val.size() > 1 && val.back() == 0) val.pop_back(); } void upd() { for (int i = 0;i < val.size();++i) { if (val[i] >= BD) { if (i+1 == val.size()) val.pb(0); val[i+1] += val[i] / BD; val[i] %= BD; } while (val[i] < 0) { --val[i+1]; val[i] += BD; } } shrink(); } bool operator < (mint b) { auto &A = val, &B = b.val; if (A.size() != B.size()) return A.size() < B.size(); for (int i = A.size() - 1;i >= 0;--i) if (A[i] != B[i]) return A[i] < B[i]; return false; } bool operator > (mint b) { return b < *this; } bool operator <= (mint b) { return !(b < *this); } friend ostream& operator << (ostream& out, mint a) { auto &val = a.val; for (int i = (int)val.size()-1;i >= 0;--i) out << setw(9) << setfill('0') << val[i]; return out; } }; mint operator - (mint a, mint b) { auto A = a.val, B = b.val; int sz = max(A.size(), B.size()); A.resize(sz), B.resize(sz); for (int i = 0;i < A.size();++i) A[i] -= B[i]; return mint(A); } mint& operator -= (mint &a, mint b) { return a = a - b; } mint operator + (mint a, mint b) { auto A = a.val, B = b.val; int sz = max(A.size(), B.size()); A.resize(sz), B.resize(sz); for (int i = 0;i < A.size();++i) A[i] += B[i]; return mint(A); } mint& operator += (mint &a, mint b) { return a = a + b; } #undef vector //#define mint ll struct node { mint sum, val; int l, r; unsigned pri; int ind; }room[MAX_N]; int new_mem(mint val = 0, int ind = 0) { static int mem; room[++mem] = {val, val, 0, 0, mrand(), ind}; return mem; } #define P(i) room[i].pri #define L(i) room[i].l #define R(i) room[i].r #define S(i) room[i].sum #define V(i) room[i].val #define ID(i) room[i].ind void upd(int ind) { S(ind) = S(L(ind)) + S(R(ind)) + V(ind); } int merge(int a, int b) { if (a == 0) return b; if (b == 0) return a; if (P(a) < P(b)) { R(a) = merge(R(a), b); upd(a); return a; } else { L(b) = merge(a, L(b)); upd(b); return b; } } void split(int root, mint sum, int &a, int &b) { if (root == 0) { a = b = 0; return; } if (S(L(root)) + V(root) <= sum) { sum -= S(L(root)) + V(root); a = root; split(R(root), sum, R(a), b); upd(a); } else { b = root; split(L(root), sum, a, L(b)); upd(b); } } vector<int> order; void dfs(int now) { if (now == 0) return; dfs(L(now)); order.pb(ID(now)); dfs(R(now)); } int32_t main() { ios_base::sync_with_stdio(0), cin.tie(0); int n; cin >> n; vector<mint> val(n); { vector<string> inp(n); for (auto &i : inp) cin >> i; for (int i = 0;i < n;++i) val[i] = mint(inp[i]); } // for (mint &a : val) { // // string v; // cin >> v; // a = mint(v); // } for (int i = n-1;i > 0;--i) { val[i] -= val[i-1]; } int root = 0; for (int i = 0;i < n;++i) { mint v = val[i] - 1; int a, b; split(root, v, a, b); int now = new_mem(val[i]); ID(now) = i; root = merge(a, merge(now, b)); } dfs(root); vector<int> ans(n); for (int i = 0;i < n;++i) { int id = order[i]; ans[id] = i+1; } for (int i = 0;i < n;++i) cout << ans[i] << " \n"[i+1==n]; }

Compilation message (stderr)

permutation.cpp: In constructor 'mint::mint(std::string)':
permutation.cpp:47:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for (int i = 0;i < s.size();++i) {
      |                  ~~^~~~~~~~~~
#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...