Submission #1101065

#TimeUsernameProblemLanguageResultExecution timeMemory
1101065Kirill22Permutation Recovery (info1cup17_permutation)C++17
43 / 100
4064 ms2764 KiB
#include "bits/stdc++.h" using namespace std; 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; } }; void solve() { mods = {998244353}; // mods = {(int) 1e9 + 7, 998244353, (int) 1e9 + 13}; 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> ord = {0}; Int all("1"); for (int i = 1; i < n; i++) { all += a[i - 1]; Int tmp = all; ord.push_back(i); if (a[i] == tmp) { continue; } for (int j = i - 1; j >= 0; j--) { tmp -= a[ord[j]]; if (a[i] == tmp) { int pos = i; while (pos != j) { swap(ord[pos - 1], ord[pos]); pos--; } break; } } } vector<int> ans(n); 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...