#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl
using namespace std;
template<typename T1, typename T2>
ostream& operator << (ostream &i, pair<T1, T2> j) {
return i << j.first << ' ' << j.second;
}
template<typename T>
ostream& operator << (ostream &i, vector<T> j) {
i << '{' << j.size() << ':';
for (T ii : j) i << ' ' << ii;
return i << '}';
}
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pp;
const int k = 300;
int cmp(string s, string t) {
if (s.length() != t.length()) return s.length() < t.length() ? -1 : 1;
if (s == t) return 0;
return s > t ? 1 : -1;
}
string add(string s, string t) {
bool c = false;
for (int i = 0; i < min(s.length(), t.length()); ++i) {
s[i] += t[i] - '0' + c;
if (s[i] > '9') s[i] -= 10, c = true;
else c = false;
t[i] = s[i];
}
if (s.length() < t.length()) {
for (int i = s.length(); i < t.length() && c; ++i) {
if (t[i] == '9') t[i] = '0';
else ++t[i], c = false;
}
if (c) t += '1';
return t;
}
for (int i = t.length(); i < s.length() && c; ++i) {
if (s[i] == '9') s[i] = '0';
else ++s[i], c = false;
}
if (c) s += '1';
return s;
}
string sub(string s, string t) {
bool c = false;
for (int i = 0; i < t.length(); ++i) {
t[i] += c;
if (s[i] >= t[i]) s[i] -= t[i] - '0', c = false;
else s[i] -= t[i] - '0' - 10, c = true;
}
for (int i = t.length(); i < s.length() && c; ++i) {
if (s[i] == '0') s[i] = '9';
else --s[i], c = false;
}
while (s.length() > 1 && s.back() == '0') s.pop_back();
return s;
}
vector<string> s;
vector<int> ans;
int it;
struct splaytree {
vector<int> v, pa;
vector<string> sz;
vector<array<int, 2>> ch;
int rt;
splaytree() : v(1, 0), pa(1, -1), sz(1, s[0]), ch(1), rt(0) {
ch[0][0] = ch[0][1] = -1;
}
void rotate(int i) {
int p = pa[i], gp = pa[p];
int x = ch[p][1] == i;
int c = ch[i][!x];
sz[p] = sub(sz[p], sz[i]);
sz[i] = add(sz[i], sz[p]);
if (~c) sz[p] = add(sz[p], sz[c]), pa[c] = p;
ch[p][x] = c, ch[i][!x] = p;
pa[p] = i, pa[i] = gp;
if (~gp) ch[gp][ch[gp][1] == p] = i;
}
void splay(int i) {
while (~pa[i]) {
if (pa[pa[i]] == -1) rotate(i);
else if (ch[pa[pa[i]]][0] == pa[i] ^ ch[pa[i]][0] == i)
rotate(i), rotate(i);
else rotate(pa[i]), rotate(i);
}
rt = i;
}
void insert(int i) {
string rem = sub(s[i], "1");
int x = rt;
while (~x) {
string pre = ~ch[x][1] ? sub(sz[x], sz[ch[x][1]]) : sz[x];
int tmp = cmp(rem, pre);
if (tmp == 1) rem = sub(rem, pre), x = ch[x][1];
else if (tmp == 0) break;
else x = ch[x][0];
}
if (x == -1) {
int id = v.size();
v.push_back(i);
pa.push_back(-1);
ch.emplace_back();
ch[id][0] = -1, ch[id][1] = rt;
sz.push_back(add(s[i], sz[rt])), pa[rt] = id;
rt = id;
return;
}
splay(x);
int id = v.size();
v.push_back(i);
pa.push_back(x);
sz[x] = add(sz[x], s[i]);
ch.emplace_back();
ch[id][0] = -1, ch[id][1] = ch[x][1];
ch[x][1] = id;
if (~ch[id][1]) sz.push_back(add(s[i], sz[ch[id][1]])), pa[ch[id][1]] = id;
else sz.push_back(s[i]);
}
void get_ans(int i = -1) {
if (i == -1) i = rt;
if (~ch[i][0]) get_ans(ch[i][0]);
ans[v[i]] = ++it;
if (~ch[i][1]) get_ans(ch[i][1]);
}
};
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n;
cin >> n;
s.resize(n);
for (string &i : s) cin >> i, reverse(all(i));
for (int i = n - 1; i; --i) s[i] = sub(s[i], s[i - 1]);
splaytree rt = splaytree();
for (int i = 1; i < n; ++i) rt.insert(i);
ans.resize(n);
rt.get_ans();
for (int i : ans) cout << i << ' ';
sort(all(ans)), ans.resize(unique(all(ans)) - ans.begin());
assert(ans.size() == n && ans[0] == 1 && ans[n - 1] == n);
}
Compilation message
permutation.cpp: In function 'std::string add(std::string, std::string)':
permutation.cpp:26:23: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
26 | for (int i = 0; i < min(s.length(), t.length()); ++i) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
permutation.cpp:33:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for (int i = s.length(); i < t.length() && c; ++i) {
| ~~^~~~~~~~~~~~
permutation.cpp:40:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for (int i = t.length(); i < s.length() && c; ++i) {
| ~~^~~~~~~~~~~~
permutation.cpp: In function 'std::string sub(std::string, std::string)':
permutation.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for (int i = 0; i < t.length(); ++i) {
| ~~^~~~~~~~~~~~
permutation.cpp:54:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for (int i = t.length(); i < s.length() && c; ++i) {
| ~~^~~~~~~~~~~~
permutation.cpp: In member function 'void splaytree::splay(int)':
permutation.cpp:86:39: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
86 | else if (ch[pa[pa[i]]][0] == pa[i] ^ ch[pa[i]][0] == i)
In file included from /usr/include/c++/9/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
from permutation.cpp:1:
permutation.cpp: In function 'int main()':
permutation.cpp:143:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
143 | assert(ans.size() == n && ans[0] == 1 && ans[n - 1] == n);
| ~~~~~~~~~~~^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
