#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 = 73;
template<class T>
struct mvec {
T a[MAX_D];
int sz = 0;
int size()const { 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); }
mvec& operator = (mvec<T> b) {
for (int i = 0;i < b.size();++i)
a[i] = b[i];
sz = b.size();
return *this;
}
};
#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
permutation.cpp: In constructor 'mint::mint(std::string)':
permutation.cpp:53:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for (int i = 0;i < s.size();++i) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
117704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
117704 KB |
Output is correct |
| 2 |
Correct |
71 ms |
117976 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
117704 KB |
Output is correct |
| 2 |
Correct |
71 ms |
117976 KB |
Output is correct |
| 3 |
Correct |
70 ms |
118208 KB |
Output is correct |
| 4 |
Correct |
68 ms |
118172 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
117704 KB |
Output is correct |
| 2 |
Correct |
71 ms |
117976 KB |
Output is correct |
| 3 |
Correct |
70 ms |
118208 KB |
Output is correct |
| 4 |
Correct |
68 ms |
118172 KB |
Output is correct |
| 5 |
Correct |
2337 ms |
147192 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
117704 KB |
Output is correct |
| 2 |
Correct |
71 ms |
117976 KB |
Output is correct |
| 3 |
Correct |
70 ms |
118208 KB |
Output is correct |
| 4 |
Correct |
68 ms |
118172 KB |
Output is correct |
| 5 |
Correct |
2337 ms |
147192 KB |
Output is correct |
| 6 |
Execution timed out |
4103 ms |
171376 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
117704 KB |
Output is correct |
| 2 |
Correct |
71 ms |
117976 KB |
Output is correct |
| 3 |
Correct |
70 ms |
118208 KB |
Output is correct |
| 4 |
Correct |
68 ms |
118172 KB |
Output is correct |
| 5 |
Correct |
2337 ms |
147192 KB |
Output is correct |
| 6 |
Execution timed out |
4103 ms |
171376 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
117704 KB |
Output is correct |
| 2 |
Correct |
71 ms |
117976 KB |
Output is correct |
| 3 |
Correct |
70 ms |
118208 KB |
Output is correct |
| 4 |
Correct |
68 ms |
118172 KB |
Output is correct |
| 5 |
Correct |
2337 ms |
147192 KB |
Output is correct |
| 6 |
Execution timed out |
4103 ms |
171376 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
117704 KB |
Output is correct |
| 2 |
Correct |
71 ms |
117976 KB |
Output is correct |
| 3 |
Correct |
70 ms |
118208 KB |
Output is correct |
| 4 |
Correct |
68 ms |
118172 KB |
Output is correct |
| 5 |
Correct |
2337 ms |
147192 KB |
Output is correct |
| 6 |
Execution timed out |
4103 ms |
171376 KB |
Time limit exceeded |
