Submission #1202466

#TimeUsernameProblemLanguageResultExecution timeMemory
1202466TahirAliyevGondola (IOI14_gondola)C++20
100 / 100
34 ms5956 KiB
#include "gondola.h" #include <bits/stdc++.h> #define ll long long #define endl "\n" using namespace std; const ll mod = 1e9 + 9; ll binpow(ll n, ll p) { ll ans = 1; n %= mod; while (p) { ans = (p & 1 ? ans * n % mod : ans); p >>= 1; n = n * n % mod; } return ans; } int valid(int n, int a[]) { set<ll> s; for (ll i = 0; i < n; i++) s.insert(a[i]); if (s.size() != n) return 0; ll st = -1, b[n]; for (ll i = 0; i < n; i++) if (a[i] <= n) st = i; if (st == -1) return 1; b[st] = a[st]; for (ll i = st + 1; i < st + n; i++) b[i % n] = b[(i - 1 + n) % n] % n + 1; // for (ll i = 0; i < n; i++) // cout << b[i] << " "; // cout << endl; for (ll i = 0; i < n; i++) if (a[i] <= n and a[i] != b[i]) return 0; return 1; } //---------------------- int replacement(int n, int a[], int replacementSeq[]) { ll st = -1, b[n]; for (ll i = 0; i < n; i++) if (a[i] <= n) st = i; if (st == -1) iota(b, b + n, 1); else { b[st] = a[st]; for (ll i = st + 1; i < st + n; i++) b[i % n] = b[(i - 1 + n) % n] % n + 1; } ll ptr = 0, mx = max_element(a, a + n) - a; ll ind[a[mx] + 1]; for (ll i = 0; i <= a[mx]; i++) ind[i] = -1; for (ll i = 0; i < n; i++) ind[a[i]] = i; for (ll i = n + 1; i <= a[mx]; i++) if (ind[i] != -1) replacementSeq[ptr++] = b[ind[i]], b[ind[i]] = i; else replacementSeq[ptr++] = b[mx], b[mx] = i; return ptr; } //---------------------- int countReplacement(int n, int a[]) { if (!valid(n, a)) return 0; ll ans = 1; ll b[n]; for (ll i = 0; i < n; i++) b[i] = a[i]; sort(b, b + n, greater()); for (ll i = 0; i < n and b[i] > n; i++) ans = ans * binpow(i + 1, b[i] - max((ll)n, i + 1 < n ? b[i + 1] : 1) - 1) % mod; if (b[n - 1] > n) ans = ans * n % mod; return ans; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...