Submission #642078

#TimeUsernameProblemLanguageResultExecution timeMemory
642078QwertyPiGondola (IOI14_gondola)C++14
100 / 100
67 ms6140 KiB
#include <bits/stdc++.h> using namespace std; #ifndef hkoi #include "gondola.h" #endif typedef long long ll; void rotate(int n, int a[], int x){ int b[n]; for(int i = 0; i < n; i++){ b[i] = a[(i + n - x) % n]; } for(int i = 0; i < n; i++){ a[i] = b[i]; } } bool init(int n, int a[]){ for(int i = 0; i < n; i++){ if(a[i] <= n){ rotate(n, a, a[i] - (i + 1)); break; } } for(int i = 0; i < n; i++){ if(a[i] <= n && a[i] != i + 1){ return false; } } set<int> S; for(int i = 0; i < n; i++){ S.insert(a[i]); } if(S.size() != n){ return false; } return true; } int valid(int n, int a[]){ return init(n, a); } //---------------------- int replacement(int n, int a[], int r[]){ init(n, a); int l = 0; vector<int> seq; for(int i = 0; i < n; i++){ seq.push_back(i + 1); } map<int, int> A; set<int> S; for(int i = 0; i < n; i++) A[a[i]] = i; for(int i = 0; i < n; i++){ if(a[i] != i + 1){ S.insert(i); } } int MAX_A = *max_element(a, a + n); for(int i = n + 1; i <= MAX_A; i++){ if(!A.count(i)){ r[l++] = seq[*S.begin()]; seq[*S.begin()] = i; }else{ r[l++] = seq[A[i]]; seq[A[i]] = i; S.erase(A[i]); } } return l; } //---------------------- const ll MOD = 1e9 + 9; ll bp(ll a, ll b){ if(b == 0) return 1; return bp(a * a % MOD, b / 2) * (b % 2 ? a : 1) % MOD; } ll mi(ll a){ return bp(a, MOD - 2); } ll C(ll n, ll r){ ll ret = 1; for(ll i = n; i >= n - r + 1; i++){ ret = (ret * i) % MOD; } for(ll i = 1; i <= r; i++){ ret = (ret * mi(i)) % MOD; } } int countReplacement(int n, int a[]){ bool ok = init(n, a); if(!ok) return 0; set<int> A; for(int i = 0; i < n; i++) A.insert(a[i]); int MAX_A = *--A.end(), MIN_A = *A.begin(); ll FIXED = 0, _prev = n, ans = MIN_A > n ? n : 1; for(auto a : A){ if(a > n){ ans = ans * bp(n - FIXED, a - _prev - 1) % MOD; _prev = a; } FIXED++; } return ans; } #ifdef hkoi int a[250001]; int b[250001]; int main() { int ST; cin >> ST; int n; cin >> n; for(int i = 0; i < n; i++) cin >> a[i]; if(1 <= ST && ST <= 3){ int ans = valid(n, a); cout << ans << '\n'; }else if(4 <= ST && ST <= 6){ int l = replacement(n, a, b); cout << l << '\n'; for(int i = 0; i < l; i++){ cout << b[i] << '\n'; } }else if(7 <= ST && ST <= 10){ int ans = countReplacement(n, a); cout << ans << '\n'; } } #endif

Compilation message (stderr)

gondola.cpp: In function 'bool init(int, int*)':
gondola.cpp:36:14: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |  if(S.size() != n){
      |     ~~~~~~~~~^~~~
gondola.cpp: In function 'll C(ll, ll)':
gondola.cpp:98:1: warning: no return statement in function returning non-void [-Wreturn-type]
   98 | }
      | ^
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:104:6: warning: unused variable 'MAX_A' [-Wunused-variable]
  104 |  int MAX_A = *--A.end(), MIN_A = *A.begin();
      |      ^~~~~
#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...