#include "bits/stdc++.h"
using namespace std;
using ll = __int128_t;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ld = long double;
using str = string;
const ld eps = 1e-8;
//#define int long long
#define vc vector
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define ff first
#define ss second
#define pb push_back
#define forn(id, num) for (int id = 0; id < num; ++id)
#define sz(arr) (int)arr.size()
#ifdef LOCAL
#define debug(x) cerr << #x << ": " << x << endl;
#else
#define debug(x)
#endif
template<typename T, typename Y>
istream& operator>>(istream &other, std::pair<T, Y> &v_) {
other >> v_.first >> v_.second; return other;
}
template<typename T, typename Y>
ostream& operator<<(ostream &other, const std::pair<T, Y> v_) {
other << v_.first << ' ' << v_.second; return other;
}
template<typename T>
istream& operator>>(istream &other, vector<T> &v_) {
for (T &x : v_) other >> x; return other;
}
template<typename T>
ostream& operator<<(ostream &other, const vector<T> v_) {
for (T &x : v_) other << x << ' '; return other;
}
template<typename T>
bool inmin(T& _x, T _y) {return _y < _x ? (_x = _y, true) : false;}
template<typename T>
bool inmax(T& _x, T _y) {return _y > _x ? (_x = _y, true) : false;}
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline void solve();
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
freopen("/Users/alexsus/Desktop/solve/read.txt", "r", stdin);
#else
#endif
//cout << fixed << setprecision(10);
ll tt;
tt = 1;
//cin >> tt;
for (int i = 0; i < tt; ++i) {
solve();
}
return 0;
}
const ll Mod = 1e9 + 7;
struct node {
node *l, *r;
ll y, val;
int id, c;
ll sm;
node (int _id, ll _val) {
y = rnd() % Mod;
l = r = nullptr;
c = 1;
id = _id, val = _val, sm = _val;
}
};
int get_c(node *x) {
if (x == nullptr) return 0;
return x->c;
}
ll get_sm(node *x) {
if (x == nullptr) return 0;
return x->sm;
}
void upd(node * x) {
if (x == nullptr) return;
x->c = 1 + get_c(x->l) + get_c(x->r);
x->sm = x->val + get_sm(x->l) + get_sm(x->r);
}
int get_x(node *x) {
return get_c(x->l);
}
pair<node *, node *> split(node *t, int key) {
if (!t) return {nullptr, nullptr};
if (get_x(t) <= key) {
pair<node *, node *> res = split(t->r, key - get_x(t) - 1);
t->r = res.ff;
upd(t);
return {t, res.ss};
} else {
pair<node *, node *> res = split(t->l, key);
t->l = res.ss;
upd(t);
return {res.ff, t};
}
}
node *merge(node *tl, node *tr) {
if (!tl) return tr;
if (!tr) return tl;
if (tl->y >= tr->y) {
tl->r = merge(tl->r, tr);
upd(tl);
return tl;
} else {
tr->l = merge(tl, tr->l);
upd(tr);
return tr;
}
}
vector<int> p;
int last;
void order(node *t) {
if (t == nullptr) return;
order(t->l);
p[t->id] = last++;
order(t->r);
}
inline void solve() {
int n;
cin >> n;
vector<ll> pref(n);
forn(i, n) {
str s;
cin >> s;
forn (j, sz(s)) {
pref[i] = 10 * pref[i] + s[j] - '0';
}
}
vector<ll> dp(n);
dp[0] = pref[0];
for (int i = 1; i < n; ++i) {
dp[i] = pref[i] - pref[i - 1];
}
node *root = new node(0, dp[0]);
for (int i = 1; i < n; ++i) {
int lhs = -1, rhs = i + 1;
while (rhs - lhs > 1) {
int mid = (lhs + rhs) / 2;
auto [l, r] = split(root, mid - 1);
ll sm = 1 + get_sm(l);
root = merge(l, r);
if (sm < dp[i]) lhs = mid;
else rhs = mid;
}
node *next = new node(i, dp[i]);
auto [l, r] = split(root, lhs);
root = merge(l, merge(next, r));
}
last = 0;
p.resize(n);
order(root);
forn(i, n) {
cout << p[i] + 1 << ' ';
}
cout << '\n';
}
Compilation message
permutation.cpp: In function 'std::istream& operator>>(std::istream&, std::vector<_Tp>&)':
permutation.cpp:38:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
38 | for (T &x : v_) other >> x; return other;
| ^~~
permutation.cpp:38:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
38 | for (T &x : v_) other >> x; return other;
| ^~~~~~
permutation.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<_Tp>)':
permutation.cpp:42:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
42 | for (T &x : v_) other << x << ' '; return other;
| ^~~
permutation.cpp:42:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
42 | for (T &x : v_) other << x << ' '; return other;
| ^~~~~~
permutation.cpp: In function 'void solve()':
permutation.cpp:164:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
164 | auto [l, r] = split(root, mid - 1);
| ^
permutation.cpp:171:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
171 | auto [l, r] = split(root, lhs);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
