#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;
struct BigInt {
vector <int> val;
BigInt(string s = "0") {
for (int i = s.length() - 1; ~i; --i) {
val.pb(s[i] - '0');
}
}
BigInt operator - (const BigInt &o) const {
vector <int> a = val;
vector <int> result(a.size());
for (int i = 0; i < o.val.size(); ++i) {
if (a[i] >= o.val[i]) result[i] = a[i] - o.val[i];
else result[i] = a[i] - o.val[i] + 10, a[i + 1]--;
}
for (int i = o.val.size(); i < a.size(); ++i) {
result[i] = a[i];
}
while (result.size() > 1 && result.back() == 0) result.pop_back();
BigInt ans;
ans.val.pop_back();
for (int i : result) ans.val.pb(i);
return ans;
}
BigInt operator + (const BigInt &o) const {
vector <int> result(max(val.size(), o.val.size()));
for (int i = 0; i < result.size(); ++i) {
int a = i < val.size() ? val[i] : 0;
int b = i < o.val.size() ? o.val[i] : 0;
result[i] = a + b;
}
for (int i = 0; i < result.size(); ++i) {
if (result[i] >= 10 && i == result.size() - 1) result.pb(0);
result[i + 1] += result[i] / 10;
result[i] %= 10;
}
BigInt ans;
ans.val.pop_back();
for (int 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;
}
} INF, one = BigInt("1"), zero;
struct Seg {
int l, r, m;
BigInt mn, lz;
Seg* ch[2];
Seg (int _l, int _r, vector <BigInt> &a) : l(_l), r(_r), m(l + r >> 1) {
if (r - l > 1) {
ch[0] = new Seg(l, m, a);
ch[1] = new Seg(m, r, a);
pull();
} else {
mn = a[l];
}
}
void pull() {
if (ch[0]->mn < ch[1]->mn) mn = ch[0]->mn;
else mn = ch[1]->mn;
}
void give(BigInt i) {
lz = lz + i;
mn = mn - i;
}
void push() {
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) {
mn = INF;
return l;
}
push();
int ans;
if (ch[1]->mn == one) ans = ch[1]->query();
else ans = ch[0]->query();
pull();
return ans;
}
};
int main () {
ios::sync_with_stdio(false);
cin.tie(0);
INF.val.pop_back();
while (INF.val.size() < 300) INF.val.pb(9);
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) {
assert(root.mn == one);
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:30:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for (int i = 0; i < o.val.size(); ++i) {
| ~~^~~~~~~~~~~~~~
permutation.cpp:34:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for (int i = o.val.size(); i < a.size(); ++i) {
| ~~^~~~~~~~~~
permutation.cpp: In member function 'BigInt BigInt::operator+(const BigInt&) const':
permutation.cpp:45:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for (int i = 0; i < result.size(); ++i) {
| ~~^~~~~~~~~~~~~~~
permutation.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | int a = i < val.size() ? val[i] : 0;
| ~~^~~~~~~~~~~~
permutation.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | int b = i < o.val.size() ? o.val[i] : 0;
| ~~^~~~~~~~~~~~~~
permutation.cpp:50:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for (int i = 0; i < result.size(); ++i) {
| ~~^~~~~~~~~~~~~~~
permutation.cpp:51:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | if (result[i] >= 10 && i == result.size() - 1) result.pb(0);
| ~~^~~~~~~~~~~~~~~~~~~~
permutation.cpp: In constructor 'Seg::Seg(int, int, std::vector<BigInt>&)':
permutation.cpp:76:66: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
76 | Seg (int _l, int _r, vector <BigInt> &a) : l(_l), r(_r), m(l + r >> 1) {
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1868 KB |
Output is correct |
| 3 |
Correct |
22 ms |
3916 KB |
Output is correct |
| 4 |
Correct |
21 ms |
3852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1868 KB |
Output is correct |
| 3 |
Correct |
22 ms |
3916 KB |
Output is correct |
| 4 |
Correct |
21 ms |
3852 KB |
Output is correct |
| 5 |
Runtime error |
403 ms |
182180 KB |
Execution killed with signal 6 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1868 KB |
Output is correct |
| 3 |
Correct |
22 ms |
3916 KB |
Output is correct |
| 4 |
Correct |
21 ms |
3852 KB |
Output is correct |
| 5 |
Runtime error |
403 ms |
182180 KB |
Execution killed with signal 6 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1868 KB |
Output is correct |
| 3 |
Correct |
22 ms |
3916 KB |
Output is correct |
| 4 |
Correct |
21 ms |
3852 KB |
Output is correct |
| 5 |
Runtime error |
403 ms |
182180 KB |
Execution killed with signal 6 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1868 KB |
Output is correct |
| 3 |
Correct |
22 ms |
3916 KB |
Output is correct |
| 4 |
Correct |
21 ms |
3852 KB |
Output is correct |
| 5 |
Runtime error |
403 ms |
182180 KB |
Execution killed with signal 6 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1868 KB |
Output is correct |
| 3 |
Correct |
22 ms |
3916 KB |
Output is correct |
| 4 |
Correct |
21 ms |
3852 KB |
Output is correct |
| 5 |
Runtime error |
403 ms |
182180 KB |
Execution killed with signal 6 |
