Submission #1101236

#TimeUsernameProblemLanguageResultExecution timeMemory
1101236Kirill22Permutation Recovery (info1cup17_permutation)C++17
43 / 100
948 ms2608 KiB
#include "bits/stdc++.h" using namespace std; //const int MOD = (int) 1e9 + 7; 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; } }; constexpr int mod = 998244353; int normalize(int x) { if (x >= mod) { x -= mod; } if (x < 0) { x += mod; } return x; } template<typename T> T power(T a, long long n) { T res = 1; for (; n; n /= 2, a *= a) { if (n % 2) { res *= a; } } return res; } class Mint { public: int x; Mint(int x = 0) : x(normalize(x)) {} Mint(long long x) : x(normalize(x % mod)) {} int val() const { return x; } Mint operator-() const { return Mint(normalize(mod - x)); } Mint inv() const { return power(*this, mod - 2); } Mint& operator*=(const Mint& rhs) { x = x * 1ll * rhs.x % mod; return *this; } Mint& operator+=(const Mint& rhs) { x = normalize(x + rhs.x); return *this; } Mint& operator-=(const Mint& rhs) { x = normalize(x - rhs.x); return *this; } Mint& operator/=(const Mint& rhs) { return *this *= rhs.inv(); } friend Mint operator*(const Mint& lhs, const Mint& rhs) { Mint res = lhs; res *= rhs; return res; } friend Mint operator+(const Mint& lhs, const Mint& rhs) { Mint res = lhs; res += rhs; return res; } friend Mint operator-(const Mint& lhs, const Mint& rhs) { Mint res = lhs; res -= rhs; return res; } friend Mint operator/(const Mint& lhs, const Mint& rhs) { Mint res = lhs; res /= rhs; return res; } bool operator==(const Mint& rhs) const { return x == rhs.x; } }; using mint = Mint; vector<mint> fact(1, 1); vector<mint> inv_fact(1, 1); void fast(int n) { while ((int) fact.size() < n + 1) { fact.push_back(fact.back() * (int) fact.size()); } inv_fact.resize(n + 1, 1); inv_fact[n] = 1 / fact[n]; for (int i = n - 1; i >= 2; i--) { inv_fact[i] = inv_fact[i + 1] * (i + 1); } } mint C(int n, int k) { if (k < 0 || k > n) { return 0; } while ((int) fact.size() < n + 1) { fact.push_back(fact.back() * (int) fact.size()); inv_fact.push_back(fact.back().inv()); } return fact[n] * inv_fact[k] * inv_fact[n - k]; } string to_string(mint x) { return to_string(x.x); } void solve() { mods = {998244353}; // mods = {(int) 1e9 + 7, 998244353, (int) 1e9 + 13}; int n; cin >> n; vector<mint> a(n); for (int i = 0; i < n; i++) { string s; cin >> s; a[i] = 0; for (auto& c : s) { a[i] = a[i] * 10 + c - '0'; } } 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<int, int>> dp(C); auto rebuild = [&] (int b) { dp[b].clear(); mint sum = 0; dp[b][sum.x] = 0; int cnt = 0; for (auto i : block[b]) { sum += a[i]; dp[b][sum.x] = ++cnt; } res[b] = sum.x; }; 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++) { mint need = a[i] - 1; for (int j = 0; ; j++) { if (j >= C) { vector<int> ord; for (auto& b : block) { for (auto& i : b) { ord.push_back(i); } } mint sum = 1; assert(need.x != sum.x); for (auto i : ord) { sum += a[i]; assert(need.x != sum.x); } exit(0); } if (dp[j].find(need.x) != dp[j].end()) { int pos = dp[j][need.x]; 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...