Submission #374585

#TimeUsernameProblemLanguageResultExecution timeMemory
374585vishesh312Gondola (IOI14_gondola)C++17
60 / 100
39 ms5300 KiB
#include "bits/stdc++.h" using namespace std; #include "gondola.h" int valid(int n, int arr[]) { map<int, bool> mp; vector<int> v(arr, arr+n); auto it = min_element(v.begin(), v.end()); rotate(v.begin(), it, v.end()); for (int i = 0; i < n; ++i) { if (mp[v[i]]) return 0; mp[v[i]] = true; if (v[i] <= n and i != v[i] - v[0]) return 0; } return 1; } int replacement(int n, int a[], int b[]) { vector<int> v(a, a+n); auto it = min_element(v.begin(), v.end()); int mn = *it, pos = it - v.begin(), mx = *max_element(v.begin(), v.end()); rotate(v.begin(), v.begin() + (pos - mn%n + 1 + n) % n, v.end()); map<int, int> mp; for (int i = 0; i < n; ++i) { mp[v[i]] = i+1; } for (int i = n+1; i <= mx; ++i) { if (mp.count(i)) b[i-n-1] = mp[i]; else { b[i-n-1] = mp[mx]; mp[mx] = i; } } return mx - n; } using ll = long long; const ll mod = 1e9+7; #define sz(x) (int)x.size() ll binexp(ll a, ll b) { assert(b >= 0); a %= mod; ll ret = 1; while (b > 0) { if (b&1) { ret = (ret * a) % mod; } a = (a * a) % mod; b >>= 1; } return ret; } int countReplacement(int n, int a[]) { vector<int> v(a, a+n); auto it = min_element(v.begin(), v.end()); rotate(v.begin(), it, v.end()); vector<int> v2 = v; sort(v2.begin(), v2.end()); for (int i = 0; i < n-1; ++i) { if (v2[i] == v2[i+1]) return 0; } for (int i = 0; i < n; ++i) { if (v[i] <= n and i != v[i] - v[0]) return 0; } ll ans; if (v2[0] > n) ans = n; else ans = 1; vector<int> bigger; bigger.push_back(n); for (int i = 0; i < n; ++i) if (v[i] > n) bigger.push_back(v[i]); sort(bigger.begin(), bigger.end()); for (int i = 1; i < sz(bigger); ++i) { ans = (ans * binexp(sz(bigger) - i, bigger[i] - bigger[i-1] - 1)) % mod; } int ret = ans; return ret; }
#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...