Submission #1025107

#TimeUsernameProblemLanguageResultExecution timeMemory
1025107nvujicaGondola (IOI14_gondola)C++14
90 / 100
19 ms2776 KiB
#include <bits/stdc++.h> #include "gondola.h" #define ll long long #define fi first #define se second using namespace std; const int maxn = 3e5 + 10, mod = 1e9 + 9, LOG = 30; int a[maxn]; int bio[maxn]; vector <pair<int, int> > v; int pot[LOG]; int mul(int x, int y){ return ((ll)x * y) % mod; } int valid(int n, int inputSeq[]){ for(int i = 0; i < n; i++){ a[i] = inputSeq[i] - 1; if(bio[a[i]]) return 0; bio[a[i]] = 1; } for(int i = 0; i < n; i++){ if(a[i] < n){ for(int j = 0; j < n; j++){ if(a[(i + j) % n] < n){ if(a[(i + j) % n] != (a[i] + j) % n) return 0; } } break; } } return 1; } int replacement(int n, int gondolaSeq[], int replacementSeq[]){ for(int i = 0; i < n; i++){ a[i] = gondolaSeq[i]; } for(int i = 0; i < n; i++){ if(a[i] > n) v.push_back({a[i], i}); } for(int i = n - 1; i >= 0; i--){ if(a[i] <= n || !i){ for(int j = 0; j < n; j++){ a[(i + j) % n] = (a[i] - 1 + j) % n + 1; } break; } } // cout << v.size() << endl; sort(v.begin(), v.end()); int p = 0, l = 0; while(p < v.size()){ replacementSeq[l] = a[v[p].se]; // cout << a[v[p].se] << ' '; a[v[p].se] = n + l + 1; l++; if(a[v[p].se] == v[p].fi) p++; } // cout << endl; // cout << l; return l; } int calc(int x, int p){ pot[0] = x; for(int i = 1; i < LOG; i++){ pot[i] = mul(pot[i - 1], pot[i - 1]); } int ret = 1; for(int i = 0; i < LOG; i++){ if(p & (1 << i)) ret = mul(ret, pot[i]); } return ret; } int countReplacement(int n, int inputSeq[]){ if(!valid(n, inputSeq)) return 0; for(int i = 0; i < n; i++){ a[i] = inputSeq[i]; } for(int i = 0; i < n; i++){ if(a[i] > n) v.push_back({a[i], i}); } // for(int i = n - 1; i >= 0; i--){ // if(a[i] <= n || !i){ // for(int j = 0; j < n; j++){ // a[(i + j) % n] = (a[i] - 1 + j) % n + 1; // } // break; // } // } // cout << v.size() << endl; // cout << v.size() << endl; // if(v.size() == 0) return 1; sort(v.begin(), v.end()); // for(int i = 0; i < v.size(); i++){ // cout << v[i].fi << ' ' << v[i].se << endl; // } int p = 0, l = n, ans = 1; // while(p < v.size()){ // l++; // if(a[v[p].se] == l){ // p++; // continue; // } // ans = mul(ans, v.size() - p); // } int zad = n; for(int i = 0; i < v.size(); i++){ // cout << v[i].fi << ' ' << zad << ": "; // cout << v.size() - i << ' ' << v[i].fi - zad - 1 << endl; ans = mul(ans, calc(v.size() - i, v[i].fi - zad - 1)); zad = v[i].fi; } // cout << endl; // cout << l; if(v.size() == n) ans = mul(ans, n); return ans; } //int main(){ // ios_base::sync_with_stdio(0); // cin.tie(0); // // int n; // cin >> n; // int inputSeq[n]; // for(int i = 0; i < n; i++){ // cin >> inputSeq[i]; // } // cout << countReplacement(n, inputSeq); // // return 0; //}

Compilation message (stderr)

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:67:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  while(p < v.size()){
      |        ~~^~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:141:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |  for(int i = 0; i < v.size(); i++){
      |                 ~~^~~~~~~~~~
gondola.cpp:151:14: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  151 |  if(v.size() == n) ans = mul(ans, n);
      |     ~~~~~~~~~^~~~
gondola.cpp:128:6: warning: unused variable 'p' [-Wunused-variable]
  128 |  int p = 0, l = n, ans = 1;
      |      ^
gondola.cpp:128:13: warning: unused variable 'l' [-Wunused-variable]
  128 |  int p = 0, l = n, ans = 1;
      |             ^
#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...