#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;
for (int i = s.length() - 1; ~i; --i)
if (s[i] != t[i]) return s[i] < t[i] ? -1 : 1;
return 0;
}
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;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n;
cin >> n;
assert(n < 70000);
string s[n], _1(1, '1');
for (string &i : s) cin >> i, reverse(all(i));
for (int i = n - 1; i; --i) s[i] = sub(s[i], s[i - 1]);
vector<string> v;
vector<deque<int>> blk;
v.push_back(s[0]);
blk.emplace_back(1, 0);
for (int i = 1; i < n; ++i) {
string rem = sub(s[i], _1);
int pf;
if (rem == "0") {
pf = 0;
blk[0].push_front(i), v[0] = add(v[0], s[i]);
goto out;
}
for (int j = 0; j < blk.size(); ++j) {
int tmp = cmp(rem, v[j]);
if (tmp == 1) rem = sub(rem, v[j]);
else if (tmp == 0) {
if (blk[j].size() < k) {
blk[j].push_back(i), v[j] = add(v[j], s[i]);
goto nxt;
}
if (j == blk.size() - 1) {
blk.emplace_back(1, i), v.push_back(s[i]);
goto nxt;
}
pf = j + 1;
blk[j + 1].push_front(i), v[j + 1] = add(v[j + 1], s[i]);
break;
}
else {
for (int ii = 0; ii < blk[j].size(); ++ii) {
tmp = cmp(rem, s[blk[j][ii]]);
if (tmp == 1) rem = sub(rem, s[blk[j][ii]]);
else {
int x = i;
for (++ii; ii < blk[j].size(); ++ii) swap(blk[j][ii], x);
blk[j].push_back(x);
v[j] = add(v[j], s[i]);
pf = j;
goto out;
}
}
}
}
out:
while (blk[pf].size() > k) {
int x = blk[pf].back();
blk[pf].pop_back();
v[pf] = sub(v[pf], s[x]);
++pf;
if (pf == blk.size()) {
blk.emplace_back(1, x);
v.push_back(s[x]);
}
else blk[pf].push_front(x), v[pf] = add(v[pf], s[x]);
}
nxt: ;
}
vector<int> ans(n);
int it = 0;
for (auto i : blk) for (int j : i) ans[j] = ++it;
for (int i : ans) cout << i << ' ';
}
Compilation message
permutation.cpp: In function 'std::string add(std::string, std::string)':
permutation.cpp:27:23: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
27 | for (int i = 0; i < min(s.length(), t.length()); ++i) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
permutation.cpp:34:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for (int i = s.length(); i < t.length() && c; ++i) {
| ~~^~~~~~~~~~~~
permutation.cpp:41:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for (int i = t.length(); i < s.length() && c; ++i) {
| ~~^~~~~~~~~~~~
permutation.cpp: In function 'std::string sub(std::string, std::string)':
permutation.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for (int i = 0; i < t.length(); ++i) {
| ~~^~~~~~~~~~~~
permutation.cpp:55:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for (int i = t.length(); i < s.length() && c; ++i) {
| ~~^~~~~~~~~~~~
permutation.cpp: In function 'int main()':
permutation.cpp:82:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::deque<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for (int j = 0; j < blk.size(); ++j) {
| ~~^~~~~~~~~~~~
permutation.cpp:90:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::deque<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | if (j == blk.size() - 1) {
| ~~^~~~~~~~~~~~~~~~~
permutation.cpp:99:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for (int ii = 0; ii < blk[j].size(); ++ii) {
| ~~~^~~~~~~~~~~~~~~
permutation.cpp:104:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for (++ii; ii < blk[j].size(); ++ii) swap(blk[j][ii], x);
| ~~~^~~~~~~~~~~~~~~
permutation.cpp:119:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::deque<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | if (pf == blk.size()) {
| ~~~^~~~~~~~~~~~~
permutation.cpp:76:13: warning: 'pf' may be used uninitialized in this function [-Wmaybe-uninitialized]
76 | int pf;
| ^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
6 ms |
332 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
6 ms |
332 KB |
Output is correct |
| 3 |
Correct |
27 ms |
408 KB |
Output is correct |
| 4 |
Correct |
35 ms |
332 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
6 ms |
332 KB |
Output is correct |
| 3 |
Correct |
27 ms |
408 KB |
Output is correct |
| 4 |
Correct |
35 ms |
332 KB |
Output is correct |
| 5 |
Execution timed out |
4065 ms |
6792 KB |
Time limit exceeded |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
6 ms |
332 KB |
Output is correct |
| 3 |
Correct |
27 ms |
408 KB |
Output is correct |
| 4 |
Correct |
35 ms |
332 KB |
Output is correct |
| 5 |
Execution timed out |
4065 ms |
6792 KB |
Time limit exceeded |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
6 ms |
332 KB |
Output is correct |
| 3 |
Correct |
27 ms |
408 KB |
Output is correct |
| 4 |
Correct |
35 ms |
332 KB |
Output is correct |
| 5 |
Execution timed out |
4065 ms |
6792 KB |
Time limit exceeded |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
6 ms |
332 KB |
Output is correct |
| 3 |
Correct |
27 ms |
408 KB |
Output is correct |
| 4 |
Correct |
35 ms |
332 KB |
Output is correct |
| 5 |
Execution timed out |
4065 ms |
6792 KB |
Time limit exceeded |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
6 ms |
332 KB |
Output is correct |
| 3 |
Correct |
27 ms |
408 KB |
Output is correct |
| 4 |
Correct |
35 ms |
332 KB |
Output is correct |
| 5 |
Execution timed out |
4065 ms |
6792 KB |
Time limit exceeded |
