#include <iostream>
#include <unordered_map>
using namespace std;
const long long MOD = 9999999999999937LL;
const long long P = 10;
const int MAX_N = 7e4 + 5;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
long long lastH = 0;
long long diff[MAX_N];
for (int i = 0; i < n; i++) {
string s;
cin >> s;
long long h = 0;
for (int j = 0; j < (int)s.size(); j++) {
h = (h * P + (s[j] - '0')) % MOD;
}
diff[i] = (h - lastH + MOD) % MOD;
lastH = h;
}
const int len = (int)sqrt(n) + 1;
long long hSum = 1;
long long need[MAX_N];
unordered_map<long long, int> st[MAX_N];
for (int i = 0; i < n; i++) {
need[i] = (hSum - diff[i] + MOD) % MOD;
st[i / len][need[i]] = i;
hSum = (hSum + diff[i]) % MOD;
}
bool stat[MAX_N];
long long push[MAX_N];
int result[MAX_N];
fill(stat, stat + MAX_N, true);
fill(push, push + MAX_N, 0LL);
fill(result, result + MAX_N, 0);
const int maxSegmIndex = (n - 1) / len;
for (int j = n; j > 0; j--) {
int pos = 0;
for (int index = maxSegmIndex; index >= 0; index--) {
if (st[index].find(push[index]) != st[index].end()) {
pos = st[index][push[index]];
break;
}
}
result[pos] = j;
stat[pos] = false;
const int segmIndex = pos / len;
const int l = segmIndex * len;
const int r = min(n, l + len);
st[segmIndex].clear();
for (int i = l; i < r; i++) {
if (!stat[i]) {
continue;
}
if (i > pos) {
need[i] = (need[i] - diff[pos] + MOD) % MOD;
}
st[segmIndex][need[i]] = i;
}
for (int ind = segmIndex + 1; ind <= maxSegmIndex; ind++) {
push[ind] = (push[ind] + diff[pos]) % MOD;
}
}
for (int i = 0; i < n; i++) {
cout << result[i] << ' ';
}
return 0;
}
Compilation message
permutation.cpp: In function 'int main()':
permutation.cpp:33:26: error: 'sqrt' was not declared in this scope
33 | const int len = (int)sqrt(n) + 1;
| ^~~~
