Submission #97275

#TimeUsernameProblemLanguageResultExecution timeMemory
97275popovicirobertPermutation Recovery (info1cup17_permutation)C++14
100 / 100
3796 ms121836 KiB
#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 ll MOD = 9999999999999937LL; const int MAXN = 100000; inline void mod(ll &x) { if(x >= MOD) x -= MOD; } ll dif[MAXN + 1], aux[MAXN + 1]; string str; const int B = 300; unordered_multiset <ll> fr[MAXN]; ll lazy[MAXN]; 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; ll last = 0; for(i = 0; i < n; i++) { cin >> str; ll cur = 0; for(auto it : str) { cur = (1LL * cur * 10 + it - '0') % MOD; } dif[i] = cur - last + MOD; mod(dif[i]); last = cur; } for(i = 0; i < n; i++) { fr[i / B].insert(dif[i]); aux[i] = dif[i]; } vector <int> sol(n); for(int tt = 1; tt <= n; tt++) { i = (n - 1) / B; while(i >= 0) { ll cur = 1 + lazy[i]; mod(cur); if(fr[i].find(cur) != fr[i].end()) { break; } i--; } int pos = -1; for(j = min(n - 1, (i + 1) * B - 1); j >= i * B; j--) { if(sol[j]) { continue; } ll cur = aux[j] - lazy[i] + MOD; mod(cur); if(cur == 1) { pos = j; break; } } sol[pos] = tt; /*if(fr[i].find(aux[pos]) == fr[i].end()) { while(1) { } }*/ fr[i].erase(fr[i].find(aux[pos])); for(j = pos + 1; j < min(n, (i + 1) * B); j++) { if(sol[j]) { continue; } /*if(fr[i].find(aux[j]) == fr[i].end()) { while(1) { } }*/ fr[i].erase(fr[i].find(aux[j])); aux[j] += MOD - dif[pos]; mod(aux[j]); fr[i].insert(aux[j]); } i++; while(i < (n - 1) / B) { lazy[i] += dif[pos]; mod(lazy[i]); i++; } for(j = i * B; j < n; j++) { if(sol[j]) { continue; } /*if(fr[i].find(aux[j]) == fr[i].end()) { while(1) { } }*/ fr[i].erase(fr[i].find(aux[j])); aux[j] += MOD - dif[pos]; mod(aux[j]); fr[i].insert(aux[j]); } } for(i = 0; i < n; i++) { cout << sol[i] << " "; } //cin.close(); //cout.close(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...