// #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
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 time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
6860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
6860 KB |
Output is correct |
| 2 |
Correct |
7 ms |
6860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
6860 KB |
Output is correct |
| 2 |
Correct |
7 ms |
6860 KB |
Output is correct |
| 3 |
Correct |
7 ms |
6988 KB |
Output is correct |
| 4 |
Correct |
9 ms |
6988 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
6860 KB |
Output is correct |
| 2 |
Correct |
7 ms |
6860 KB |
Output is correct |
| 3 |
Correct |
7 ms |
6988 KB |
Output is correct |
| 4 |
Correct |
9 ms |
6988 KB |
Output is correct |
| 5 |
Correct |
935 ms |
15620 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
6860 KB |
Output is correct |
| 2 |
Correct |
7 ms |
6860 KB |
Output is correct |
| 3 |
Correct |
7 ms |
6988 KB |
Output is correct |
| 4 |
Correct |
9 ms |
6988 KB |
Output is correct |
| 5 |
Correct |
935 ms |
15620 KB |
Output is correct |
| 6 |
Correct |
1901 ms |
25528 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
6860 KB |
Output is correct |
| 2 |
Correct |
7 ms |
6860 KB |
Output is correct |
| 3 |
Correct |
7 ms |
6988 KB |
Output is correct |
| 4 |
Correct |
9 ms |
6988 KB |
Output is correct |
| 5 |
Correct |
935 ms |
15620 KB |
Output is correct |
| 6 |
Correct |
1901 ms |
25528 KB |
Output is correct |
| 7 |
Correct |
1567 ms |
33392 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
6860 KB |
Output is correct |
| 2 |
Correct |
7 ms |
6860 KB |
Output is correct |
| 3 |
Correct |
7 ms |
6988 KB |
Output is correct |
| 4 |
Correct |
9 ms |
6988 KB |
Output is correct |
| 5 |
Correct |
935 ms |
15620 KB |
Output is correct |
| 6 |
Correct |
1901 ms |
25528 KB |
Output is correct |
| 7 |
Correct |
1567 ms |
33392 KB |
Output is correct |
| 8 |
Correct |
1234 ms |
143012 KB |
Output is correct |
| 9 |
Correct |
2613 ms |
114508 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
6860 KB |
Output is correct |
| 2 |
Correct |
7 ms |
6860 KB |
Output is correct |
| 3 |
Correct |
7 ms |
6988 KB |
Output is correct |
| 4 |
Correct |
9 ms |
6988 KB |
Output is correct |
| 5 |
Correct |
935 ms |
15620 KB |
Output is correct |
| 6 |
Correct |
1901 ms |
25528 KB |
Output is correct |
| 7 |
Correct |
1567 ms |
33392 KB |
Output is correct |
| 8 |
Correct |
1234 ms |
143012 KB |
Output is correct |
| 9 |
Correct |
2613 ms |
114508 KB |
Output is correct |
| 10 |
Correct |
2974 ms |
164216 KB |
Output is correct |
