#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44
using namespace std;
const int MOD1 = 666013;
const int MOD2 = 666019;
const int MAXN = 70000;
inline void mod(int &x, int md) {
if(x >= md)
x -= md;
}
inline void add(pair <int, int> &a, pair <int, int> b) {
a.first += b.first;
mod(a.first, MOD1);
a.second += b.second;
mod(a.second, MOD2);
}
inline void sub(pair <int, int> &a, pair <int, int> b) {
a.first += MOD1 - b.first;
mod(a.first, MOD1);
a.second += MOD2 - b.second;
mod(a.second, MOD2);
}
pair <int, int> dif[MAXN + 1], aux[MAXN + 1];
string str;
const int B = 300;
map < pair <int, int>, int > fr[B];
pair <int, int> lazy[B];
int main() {
//ifstream cin("A.in");
//ofstream cout("A.out");
int i, j, n;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
pair <int, int> last = {0, 0};
for(i = 0; i < n; i++) {
cin >> str;
pair <int, int> cur = {0, 0};
for(auto it : str) {
cur.first = (cur.first * 10 + it - '0') % MOD1;
cur.second = (cur.second * 10 + it - '0') % MOD2;
}
dif[i] = cur;
sub(dif[i], last);
last = cur;
}
for(i = 0; i < n; i++) {
fr[i / B][dif[i]]++;
aux[i] = dif[i];
}
vector <int> sol(n);
for(int tt = 1; tt <= n; tt++) {
i = (n - 1) / B;
while(i > 0) {
pair <int, int> x = {1, 1};
add(x, lazy[i]);
if(fr[i][x]) {
fr[i][x]--;
break;
}
i--;
}
int pos;
for(j = min(n - 1, (i + 1) * B - 1); j >= i * B; j--) {
if(sol[j]) {
continue;
}
pair <int, int> cur = aux[j];
sub(cur, lazy[i]);
if(cur.first == 1 && cur.second == 1) {
pos = j;
break;
}
}
sol[pos] = tt;
for(j = pos; j < min(n, (i + 1) * B); j++) {
fr[i][aux[j]]--;
sub(aux[j], dif[pos]);
fr[i][aux[j]]++;
}
i++;
while(i < (n - 1) / B) {
add(lazy[i], dif[pos]);
i++;
}
for(j = i * B; j < n; j++) {
fr[i][aux[j]]--;
sub(aux[j], dif[pos]);
fr[i][aux[j]]++;
}
}
for(i = 0; i < n; i++) {
cout << sol[i] << " ";
}
//cin.close();
//cout.close();
return 0;
}
Compilation message
permutation.cpp: In function 'int main()':
permutation.cpp:78:13: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
int pos;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
1536 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
1536 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
1536 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
1536 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
1536 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
1536 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
1536 KB |
Output isn't correct |
