Submission #389644

#TimeUsernameProblemLanguageResultExecution timeMemory
3896442qbingxuanPermutation Recovery (info1cup17_permutation)C++14
100 / 100
2974 ms164216 KiB
// #define _GLIBCXX_DEBUG #pragma GCC optimize("Ofast") #include <bits/stdc++.h> #ifdef local #define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n" #define pary(a...) danb(#a, a) #define debug(a...) qqbx(#a, a) template <typename ...T> void qqbx(const char *s, T ...a) { int cnt = sizeof...(T); ((std::cerr << "\033[1;32m(" << s << ") = (") , ... , (std::cerr << a << (--cnt ? ", " : ")\033[0m\n"))); } template <typename T> void danb(const char *s, T L, T R) { std::cerr << "\033[1;32m[ " << s << " ] = [ "; for (int f = 0; L != R; ++L) std::cerr << (f++ ? ", " : "") << *L; std::cerr << " ]\033[0m\n"; } #else #define debug(...) ((void)0) #define safe ((void)0) #define pary(...) ((void)0) #endif // local #define all(v) begin(v),end(v) #define pb emplace_back using namespace std; using ll = int64_t; const int maxn = 70025; struct BigInteger : vector<int> { static constexpr int base = 1000000000; static constexpr int width = 9; BigInteger() {} explicit BigInteger(int x) : vector<int>{x} {} friend istream & operator>>(istream &I, BigInteger &n) { string s; I >> s; n.reserve(s.size() / 9); reverse(s.begin(), s.end()); int cur = 0, cnt = 0, p = 1; for (char c: s) { cur = cur + (c - '0') * p; if (++cnt == width) { n.emplace_back(cur); cur = 0; cnt = 0; p = 1; } else { p *= 10; } } if (cnt) n.emplace_back(cur); return I; } BigInteger& operator+=(const BigInteger &rhs) { if (size() < rhs.size()) resize(rhs.size()); int carry = 0; for (size_t i = 0; i < size(); i++) { at(i) += (i < rhs.size() ? rhs[i] : 0) + carry; carry = at(i) / base; at(i) %= base; } if (carry) push_back(carry); return *this; } BigInteger& operator-=(const BigInteger &rhs) { int carry = 0; for (size_t i = 0; i < size(); i++) { at(i) -= (i < rhs.size() ? rhs[i] : 0) + carry; if (at(i) < 0) { at(i) += base; carry = 1; } else { carry = 0; } } while (!empty() && back() == 0) pop_back(); return *this; } friend bool operator<(const BigInteger &x, const BigInteger &y) { if (x.size() != y.size()) return x.size() < y.size(); if (x.empty()) return false; for (int i = x.size()-1; i >= 0; i--) if (x[i] != y[i]) return x[i] < y[i]; return false; } friend bool operator>=(const BigInteger &x, const BigInteger &y) { return !(x < y); } friend bool operator>(const BigInteger &x, const BigInteger &y) { return y < x; } friend bool operator<=(const BigInteger &x, const BigInteger &y) { return !(y < x); } friend BigInteger operator+(BigInteger a, const BigInteger &b) { return a += b; } friend BigInteger operator-(BigInteger a, const BigInteger &b) { return a -= b; } friend ostream & operator<<(ostream &O, BigInteger n) { return O << n[0]; } }; vector<int> ans; using Int = BigInteger; struct Splay { struct node { int pa, ch[2]; Int sum, val; int id; node() : pa(0), ch{0, 0}, sum(), val(), id() {} node(const Int & x, int pos) : pa(0), ch{0, 0}, sum(x), val(x), id(pos) {} } S[maxn]; int tot; bool dir(int x) { return S[S[x].pa].ch[1] == x; } bool isRoot(int x) { return !x || !S[x].pa; } void pull(int x) { S[x].sum = S[S[x].ch[0]].sum + S[x].val + S[S[x].ch[1]].sum; } void rot(int x) { debug("rot", x); int y = S[x].pa, z = S[y].pa, d = dir(x); S[x].pa = z; if (!isRoot(y)) S[z].ch[dir(y)] = x; S[y].ch[d] = S[x].ch[!d]; if (S[x].ch[!d]) S[S[x].ch[!d]].pa = y; S[y].pa = x; S[x].ch[!d] = y; pull(y); pull(x); } void splay(int x) { // debug("splay", x); while (!isRoot(x)) { if (int y = S[x].pa; !isRoot(y)) rot(dir(x) != dir(y) ? x : y); rot(x); } } int endPoint(int x, bool d) { debug(x); while (S[x].ch[d]) x = S[x].ch[d]; return x; } void insert(Int sum, int idx) { S[++tot] = node(sum, idx); if (tot == 1) return; if (sum == static_cast<Int>(1)) { safe; debug(sum, idx, "FRONT"); splay(tot-1); int x = endPoint(tot-1, false); S[x].ch[0] = tot; S[tot].pa = x; pull(x); splay(tot); return; } int x = tot-1; splay(x); debug(x, sum); // dfs(x), cerr << '\n'; int cnt=0; while (true) { // if (++cnt>=20) exit(0); debug(x, "IN"); Int cur = S[S[x].ch[0]].sum + S[x].val; debug(cur+BigInteger(1), sum); if (cur + BigInteger(1) < sum) { sum -= cur; x = S[x].ch[1]; } else if (cur + BigInteger(1) > sum) { x = S[x].ch[0]; } else break; } splay(x); debug("POS", x); if (S[x].ch[1] == 0) { S[x].ch[1] = tot; S[tot].pa = x; pull(x); } else { int y = endPoint(S[x].ch[1], false); S[y].ch[0] = tot; S[tot].pa = y; pull(y); splay(tot); } } void dfs(int x) { if (!x) return; dfs(S[x].ch[0]); // cerr << S[x].id << ',' << S[x].val << ' '; ans.pb(S[x].id); dfs(S[x].ch[1]); } } sp; Int q[maxn]; signed main() { debug(0); ios_base::sync_with_stdio(0), cin.tie(0); int n; cin >> n; for (int i = 0; i < n; i++) cin >> q[i]; for (int i = n-1; i >= 1; i--) q[i] -= q[i-1]; for (int i = 0; i < n; i++) { sp.insert(q[i], i); debug(i); // sp.splay(1); // sp.dfs(1); // cerr << '\n'; } sp.splay(1); sp.dfs(1); // return 0; /* vector<int> ans{0}; for (int i = 1; i < n; i++) { // pary(q[i].begin(), q[i].end()); if (q[i] == static_cast<Int>(1)) { ans.insert(ans.begin(), i); continue; } Int sum = static_cast<Int>(1); for (int j = 0; j < i; j++) { sum += q[ans[j]]; // pary(sum.begin(), sum.end()); if (sum == q[i]) { ans.insert(ans.begin() + j + 1, i); break; } } } */ vector<int> p(n); for (int i = 0; i < n; i++) p[ans[i]] = i+1; for (int i = 0; i < n; i++) cout << p[i] << (i+1==n ? '\n' : ' '); }

Compilation message (stderr)

permutation.cpp: In member function 'void Splay::splay(int)':
permutation.cpp:139:17: warning: init-statement in selection statements only available with '-std=c++17' or '-std=gnu++17'
  139 |             if (int y = S[x].pa; !isRoot(y))
      |                 ^~~
permutation.cpp: In member function 'void Splay::insert(Int, int)':
permutation.cpp:168:13: warning: unused variable 'cnt' [-Wunused-variable]
  168 |         int cnt=0;
      |             ^~~
#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...