#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define test(x) cout << #x << ' ' << x << endl
#define printv(x) { \
for (auto a : x) cout << a << ' '; \
cout << endl; \
}
#define pii pair<int, int>
#define pll pair<lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
const int N = 512, abc = 864197532, K = 18;
const long long base = pow(10, K);
struct BigInt {
vector <lli> val;
BigInt(string s = "0") {
int cnt = 0;
lli pre = 0, pww = 1;
for (int i = s.length() - 1; ~i; --i) {
cnt++;
pre += pww * (s[i] - '0');
pww *= 10;
if (cnt == K) val.pb(pre), cnt = pre = 0, pww = 1;
}
if (cnt) val.pb(pre);
}
BigInt operator - (const BigInt &o) const {
vector <lli> result(max(val.size(), o.val.size()));
for (int i = 0; i < result.size(); ++i) {
lli a = i < val.size() ? val[i] : 0;
lli b = i < o.val.size() ? o.val[i] : 0;
result[i] = a - b;
}
for (int i = 0; i < result.size(); ++i) {
if (result[i] < 0) {
int add = (-result[i] + base - 1) / base;
result[i + 1] -= add;
result[i] += add * base;
}
}
while (result.size() > 1 && result.back() == 0) result.pop_back();
BigInt ans;
ans.val.pop_back();
for (lli i : result) ans.val.pb(i);
return ans;
}
BigInt operator + (const BigInt &o) const {
vector <lli> result(max(val.size(), o.val.size()));
for (int i = 0; i < result.size(); ++i) {
lli a = i < val.size() ? val[i] : 0;
lli b = i < o.val.size() ? o.val[i] : 0;
result[i] = a + b;
}
for (int i = 0; i < result.size(); ++i) {
if (result[i] >= base && i == result.size() - 1) result.pb(0);
result[i + 1] += result[i] / base;
result[i] %= base;
}
while (result.size() > 1 && result.back() == 0) result.pop_back();
BigInt ans;
ans.val.pop_back();
for (lli i : result) ans.val.pb(i);
return ans;
}
bool operator == (const BigInt &o) const {
return val == o.val;
}
bool operator < (const BigInt &o) const {
if (val.size() != o.val.size()) return val.size() < o.val.size();
for (int i = val.size() - 1; ~i; --i) if (val[i] != o.val[i]) {
return val[i] < o.val[i];
}
return false;
}
} one = BigInt("1"), zero;
struct Seg {
int l, r, m, cnt;
BigInt mn, lz;
Seg* ch[2];
Seg (int _l, int _r, vector <BigInt> &a) : l(_l), r(_r), m(l + r >> 1), cnt(0) {
if (r - l > 1) {
ch[0] = new Seg(l, m, a);
ch[1] = new Seg(m, r, a);
pull();
} else {
mn = a[l];
}
}
bool INF() {
return cnt == r - l;
}
void pull() {
if (INF()) return;
if (ch[0]->INF()) mn = ch[1]->mn;
else if (ch[1]->INF()) mn = ch[0]->mn;
else if (ch[0]->mn < ch[1]->mn) mn = ch[0]->mn;
else mn = ch[1]->mn;
}
void give(BigInt i) {
if (INF()) return;
lz = lz + i;
mn = mn - i;
}
void push() {
if (INF()) return;
if (lz == zero) return;
ch[0]->give(lz), ch[1]->give(lz);
lz = zero;
}
void modify(int a, int b, BigInt v) {
if (a <= l && r <= b) give(v);
else {
push();
if (a < m) ch[0]->modify(a, b, v);
if (m < b) ch[1]->modify(a, b, v);
pull();
}
}
int query() {
if (r - l == 1) {
cnt++;
return l;
}
push();
int ans;
if (!ch[1]->INF() && ch[1]->mn == one) ans = ch[1]->query();
else ans = ch[0]->query();
pull();
cnt++;
return ans;
}
};
int main () {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector <BigInt> a;
string s;
for (int i = 0; i < n; ++i) cin >> s, a.pb(BigInt(s));
vector <BigInt> d(n);
vector <int> p(n, 0);
int now = 1;
for (int i = 0; i < n; ++i) {
d[i] = (i ? a[i] - a[i - 1] : a[i]);
}
Seg root(0, n, d);
while (now <= n) {
int i = root.query();
p[i] = now++;
root.modify(i, n, d[i]);
}
printv(p);
}
Compilation message
permutation.cpp: In member function 'BigInt BigInt::operator-(const BigInt&) const':
permutation.cpp:36:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for (int i = 0; i < result.size(); ++i) {
| ~~^~~~~~~~~~~~~~~
permutation.cpp:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | lli a = i < val.size() ? val[i] : 0;
| ~~^~~~~~~~~~~~
permutation.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | lli b = i < o.val.size() ? o.val[i] : 0;
| ~~^~~~~~~~~~~~~~
permutation.cpp:41:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for (int i = 0; i < result.size(); ++i) {
| ~~^~~~~~~~~~~~~~~
permutation.cpp: In member function 'BigInt BigInt::operator+(const BigInt&) const':
permutation.cpp:56:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for (int i = 0; i < result.size(); ++i) {
| ~~^~~~~~~~~~~~~~~
permutation.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | lli a = i < val.size() ? val[i] : 0;
| ~~^~~~~~~~~~~~
permutation.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | lli b = i < o.val.size() ? o.val[i] : 0;
| ~~^~~~~~~~~~~~~~
permutation.cpp:61:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for (int i = 0; i < result.size(); ++i) {
| ~~^~~~~~~~~~~~~~~
permutation.cpp:62:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | if (result[i] >= base && i == result.size() - 1) result.pb(0);
| ~~^~~~~~~~~~~~~~~~~~~~
permutation.cpp: In constructor 'Seg::Seg(int, int, std::vector<BigInt>&)':
permutation.cpp:88:66: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
88 | Seg (int _l, int _r, vector <BigInt> &a) : l(_l), r(_r), m(l + r >> 1), cnt(0) {
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
2 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
2 ms |
460 KB |
Output is correct |
| 3 |
Correct |
4 ms |
716 KB |
Output is correct |
| 4 |
Correct |
4 ms |
716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
2 ms |
460 KB |
Output is correct |
| 3 |
Correct |
4 ms |
716 KB |
Output is correct |
| 4 |
Correct |
4 ms |
716 KB |
Output is correct |
| 5 |
Correct |
808 ms |
27520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
2 ms |
460 KB |
Output is correct |
| 3 |
Correct |
4 ms |
716 KB |
Output is correct |
| 4 |
Correct |
4 ms |
716 KB |
Output is correct |
| 5 |
Correct |
808 ms |
27520 KB |
Output is correct |
| 6 |
Correct |
1623 ms |
52340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
2 ms |
460 KB |
Output is correct |
| 3 |
Correct |
4 ms |
716 KB |
Output is correct |
| 4 |
Correct |
4 ms |
716 KB |
Output is correct |
| 5 |
Correct |
808 ms |
27520 KB |
Output is correct |
| 6 |
Correct |
1623 ms |
52340 KB |
Output is correct |
| 7 |
Correct |
1586 ms |
58352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
2 ms |
460 KB |
Output is correct |
| 3 |
Correct |
4 ms |
716 KB |
Output is correct |
| 4 |
Correct |
4 ms |
716 KB |
Output is correct |
| 5 |
Correct |
808 ms |
27520 KB |
Output is correct |
| 6 |
Correct |
1623 ms |
52340 KB |
Output is correct |
| 7 |
Correct |
1586 ms |
58352 KB |
Output is correct |
| 8 |
Correct |
2031 ms |
196680 KB |
Output is correct |
| 9 |
Correct |
2974 ms |
169168 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
2 ms |
460 KB |
Output is correct |
| 3 |
Correct |
4 ms |
716 KB |
Output is correct |
| 4 |
Correct |
4 ms |
716 KB |
Output is correct |
| 5 |
Correct |
808 ms |
27520 KB |
Output is correct |
| 6 |
Correct |
1623 ms |
52340 KB |
Output is correct |
| 7 |
Correct |
1586 ms |
58352 KB |
Output is correct |
| 8 |
Correct |
2031 ms |
196680 KB |
Output is correct |
| 9 |
Correct |
2974 ms |
169168 KB |
Output is correct |
| 10 |
Correct |
3792 ms |
237752 KB |
Output is correct |
