Submission #1101059

#TimeUsernameProblemLanguageResultExecution timeMemory
1101059Kirill22Permutation Recovery (info1cup17_permutation)C++17
43 / 100
4054 ms2640 KiB
#include "bits/stdc++.h" using namespace std; vector<int> mods = {(int) 1e9 + 7, 998244353, (int) 1e9 + 13}; 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; } }; void solve() { mods = {998244353}; 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]; } vector<int> nxt(n, -1); int root = 0; for (int i = 1; i < n; i++) { Int tmp("1"); if (a[i] == tmp) { nxt[i] = root; root = i; continue; } int cur = root; for (int j = 0; j < i; j++) { tmp += a[cur]; if (tmp == a[i]) { nxt[i] = nxt[cur]; nxt[cur] = i; break; } cur = nxt[cur]; } } vector<int> ans(n); for (int i = 0; i < n; i++) { ans[root] = 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...