#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
/*
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
*/
#define mp make_pair
#define ll long long
#define ld long double
#define pb push_back
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fs first
#define sc second
#define getfiles ifstream cin("input.txt"); ofstream cout("output.txt");
#define endl '\n'
#define pii pair<ll, ll>
const ll INF = 2000000005;
const ll BIG_INF = 2000000000000000005;
const ll mod = 362064680345377;
const ll P = 10;
const ld PI = 3.141592653589793238462643;
const double eps = 1e-9;
using namespace std;
using namespace __gnu_pbds;
bool valid(ll x, ll y, ll n, ll m) {
return x >= 0 && y >= 0 && x < n && y < m;
}
mt19937_64 rng(1999999973);
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const ll N = 70000 + 50, K = 300;
unordered_map<ll, ll> ch[K];
ll ad[K], p[N], q[N], ans[N], need[N], n;
string s;
signed main() {
fast_io;
cin >> n;
for (ll i = 0; i < n; i++) {
cin >> s;
ll st = 1;
for (ll j = s.size() - 1; j >= 0; j--) {
q[i] += (ll)(s[j] - '0') * st;
q[i] %= mod;
st = (st * P) % mod;
}
}
ll cursum = 1;
ans[0] = 1;
for (ll i = 1; i < n; i++) {
ans[i] = (q[i] + mod - q[i - 1]) % mod;
}
for (ll i = 0; i < n; i++) {
need[i] = (cursum + mod - ans[i]) % mod;
cursum = (cursum + ans[i]) % mod;
}
for (ll i = 0; i < n; i++) {
ch[i / K][need[i]]++;
}
for (ll i = n; i >= 1; i--) {
ll bl;
for (ll block = (n - 1) / K; block >= 0; block--) {
if(ch[block].find(ad[block]) != ch[block].end()) {
bl = block;
break;
}
}
ll j = min((bl + 1) * K - 1, n - 1);
while(need[j] != ad[bl] || p[j] != 0)
j--;
ch[bl][need[j]]--;
if (ch[bl][need[j]] == 0)
ch[bl].erase(need[j]);
p[j] = i;
for (ll k = j + 1; k / K == bl && k < n; k++) {
if (p[k] != 0)
continue;
ch[bl][need[k]]--;
if (ch[bl][need[k]] == 0)
ch[bl].erase(need[k]);
need[k] = (need[k] + mod - ans[j]) % mod;
ch[bl][need[k]]++;
}
for (ll k = bl + 1; k <= (n - 1) / K; k++) {
ad[k] += ans[j];
ad[k] %= mod;
}
}
for (ll i = 0; i < n; i++)
cout << p[i] << " ";
return 0;
}
Compilation message
Compilation timeout while compiling permutation
