Submission #1101240

#TimeUsernameProblemLanguageResultExecution timeMemory
1101240Kirill22Permutation Recovery (info1cup17_permutation)C++17
100 / 100
2826 ms120752 KiB
#include "bits/stdc++.h" using namespace std; //const int MOD = (int) 1e9 + 7; const int K = 2; vector<int> mods; struct Int { vector<int> val; Int(string s = "") { for (auto& mod : mods) { int ans = 0; for (auto& c : s) { ans = (ans * 10ll + c - '0') % mod; } val.push_back(ans); } } Int& operator+=(const Int& other) { for (int i = 0; i < (int) mods.size(); i++) { val[i] += other.val[i]; if (val[i] >= mods[i]) { val[i] -= mods[i]; } } return *this; } Int& operator-=(const Int& other) { for (int i = 0; i < (int) mods.size(); i++) { val[i] -= other.val[i]; if (val[i] < 0) { val[i] += mods[i]; } } return *this; } bool operator==(const Int& other) const { return val == other.val; } long long get() const { return val[0] * 1ll * mods[1] + val[1]; } }; void solve() { // mods = {998244353}; // mods = {(int) 1e9 + 7, 998244353, (int) 1e9 + 13}; mods = {(int) 1e9 + 7, 998244353}; assert((int) mods.size() == K); int n; cin >> n; vector<Int> a(n); for (int i = 0; i < n; i++) { string s; cin >> s; a[i] = Int(s); } for (int i = n - 1; i; i--) { a[i] -= a[i - 1]; } const int B = 500, C = n / B + 1; vector<vector<int>> block(C); vector<Int> res(C); vector<unordered_map<long long, int>> dp(C); auto rebuild = [&] (int b) { dp[b].clear(); Int sum("0"); dp[b][sum.get()] = 0; int cnt = 0; for (auto i : block[b]) { sum += a[i]; dp[b][sum.get()] = ++cnt; } res[b] = sum; }; block[0].push_back(0); rebuild(0); auto Rebuild = [&] () { vector<int> ord; for (auto& b : block) { for (auto& i : b) { ord.push_back(i); } } block.clear(); block.resize(C); for (int i = 0; i < (int) ord.size(); i++) { block[i / B].push_back(ord[i]); } for (int i = 0; i < C; i++) { rebuild(i); } }; for (int i = 1; i < n; i++) { Int need = a[i]; need -= Int("1"); for (int j = 0; ; j++) { if (dp[j].find(need.get()) != dp[j].end()) { int pos = dp[j][need.get()]; block[j].insert(block[j].begin() + pos, i); rebuild(j); break; } else { need -= res[j]; } } if (i % B == 0) { Rebuild(); } } vector<int> ans(n), ord; for (auto& b : block) { for (auto& i : b) { ord.push_back(i); } } for (int i = 0; i < n; i++) { ans[ord[i]] = i; // root = nxt[root]; } for (int i = 0; i < n; i++) { cout << ans[i] + 1 << " "; } cout << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; // cin >> t; while (t--) { solve(); } }
#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...