Submission #602726

#TimeUsernameProblemLanguageResultExecution timeMemory
602726VanillaGondola (IOI14_gondola)C++17
100 / 100
62 ms6388 KiB
#include <bits/stdc++.h> #include "gondola.h" typedef long long int64; using namespace std; int valid(int n, int a[]){ map <int, int> mp; int in [n] = {}; int ps = -1; for (int i = 0; i < n; i++){ if (a[i] <= n) ps = i; } if (ps == -1){ for (int i = 0; i < n; i++) in[i] = i + 1; } else { for (int i = ps, v = a[ps]; !in[i]; i = (i + 1) % n, v = v % n + 1) in[i] = v; } for (int i = 0; i < n; i++){ mp[a[i]]++; if (mp[a[i]] > 1) return 0; } if (ps == -1) return 1; for (int i = 0; i < n; i++){ if (a[i] <= n && a[i] != in[i]) return 0; } return 1; } //---------------------- int replacement(int n, int a[], int rs[]){ const int maxv = 2e5 + 5e4; int in[n] = {}; int l = 0; int ct = n + 1; int ps = -1; vector <pair <int, int> > v; for (int i = 0; i < n; i++){ v.push_back({a[i], i}); if (a[i] <= n) ps = i; } sort(v.begin(), v.end()); if (ps == -1){ for (int i = 0; i < n; i++) in[i] = i + 1; } else { for (int i = ps, v = a[ps]; !in[i]; i = (i + 1) % n, v = v % n + 1) in[i] = v; } for (auto [val, pos]: v) { while (in[pos] != val) { rs[l++] = in[pos]; in[pos] = ct++; } } return l; } //---------------------- const int64 mod = 1e9 + 9; int64 pw (int64 a, int64 b) { if (!b) return 1; int64 h = pw (a, b / 2); return (b % 2 ? h * h % mod * a % mod: h * h % mod); } map <int, bool> is; int countReplacement(int n, int a[]){ if (!valid(n, a)) return 0; bool low = 0; vector <int> v; for (int i = 0; i < n; i++){ if (a[i] > n) v.push_back(a[i]); if (a[i] <= n) low = 1; } v.push_back(n); sort(v.begin(), v.end()); int m = v.size(); int64 rs = (low ? 1: n); for (int i = 1; i < m; i++){ int64 diff = v[i] - v[i-1] - 1; rs = rs * pw(m - i, diff) % mod; } return rs; }

Compilation message (stderr)

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:33:12: warning: unused variable 'maxv' [-Wunused-variable]
   33 |  const int maxv = 2e5 + 5e4;
      |            ^~~~
#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...