Submission #756154

#TimeUsernameProblemLanguageResultExecution timeMemory
756154minhcoolGondola (IOI14_gondola)C++17
100 / 100
59 ms10024 KiB
#include "gondola.h" #include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; //#define int long long #define fi first #define se second #define pb push_back #define mp make_pair typedef pair<int, int> ii; typedef pair<ii, int> iii; typedef pair<ii, ii> iiii; const int N = 3e5 + 5; const int oo = 1e18 + 7, mod = 1e9 + 7; mt19937 rng(1); int rnd(int l, int r){ int temp = rng() % (r - l + 1); return abs(temp) + l; } int n; int valid(int N, int inputSeq[]){ set<int> se; n = N; for(int i = 0; i < n; i++) se.insert(inputSeq[i]); if(se.size() < n) return 0; ii ind = {-1, -1}; for(int i = 0; i < n; i++){ if(inputSeq[i] <= n){ ind = {i, inputSeq[i]}; break; } } // no original gorillas if(ind.fi < 0) return 1; //set<int> se; // check if other original gorillas are compatible for(int i = ind.fi + 1; i < n; i++){ ind.se++; if(ind.se > n) ind.se = 1; if(inputSeq[i] <= n && inputSeq[i] != ind.se) return 0; } for(int i = 0; i < ind.fi; i++){ ind.se++; if(ind.se > n) ind.se = 1; if(inputSeq[i] <= n && inputSeq[i] != ind.se) return 0; } return 1; } int need[N]; int replacement(int N, int gondolaSeq[], int replacementSeq[]){ n = N; for(int i = 0; i < n; i++) need[i] = i+1; for(int i = 0; i < n; i++){ if(gondolaSeq[i] <= n){ int itr = gondolaSeq[i]; for(int j = i; j < n; j++){ need[j] = itr; itr++; if(itr > n) itr = 1; } for(int j = 0; j < i; j++){ need[j] = itr; itr++; if(itr > n) itr = 1; } break; } } set<int> se;// se saves the numbers that are not in the conversation ii mx = {-1, -1}; for(int i = 0; i < n; i++) mx = max(mx, {gondolaSeq[i], i}); for(int i = n + 1; i <= mx.fi; i++) se.insert(i); for(int i = 0; i < n; i++) se.erase(gondolaSeq[i]); mx.se = need[mx.se];// the original number for(auto it : se){ // the next number replace the last number replacementSeq[it - n - 1] = mx.se; mx.se = it; } replacementSeq[mx.fi - n - 1] = mx.se; for(int i = 0; i < n; i++){// other numbers just need to be fixed once if(gondolaSeq[i] > n && gondolaSeq[i] != (mx.fi)){ replacementSeq[gondolaSeq[i] - n - 1] = need[i]; } } //for(int i = 0; i < mx.fi - n; i++) cout << replacementSeq[i] << " "; //cout << "\n"; for(int i = 0; i < (mx.fi - n); i++) assert(replacementSeq[i] > 0); return mx.fi - n; } #define ll long long int binpw(int base, int pw, int md){ //cout << base << " " << pw << "\n"; if(pw <= 0) return 1; //cout << base << " " << pw << "\n"; ll ans = 1; while(pw){ // cout << pw << "\n"; if(pw & 1) ans = (ans * (ll)base) % md; base = ((ll)base * (ll)base) % md; pw >>= 1; } return (int)ans; } bool val(int N, int inputSeq[]){ set<int> se; n = N; for(int i = 0; i < n; i++) se.insert(inputSeq[i]); if(se.size() < n) return 0; ii ind = {-1, -1}; for(int i = 0; i < n; i++){ if(inputSeq[i] <= n){ ind = {i, inputSeq[i]}; break; } } // no original gorillas if(ind.fi < 0) return 1; //set<int> se; // check if other original gorillas are compatible for(int i = ind.fi + 1; i < n; i++){ ind.se++; if(ind.se > n) ind.se = 1; if(inputSeq[i] <= n && inputSeq[i] != ind.se) return 0; } for(int i = 0; i < ind.fi; i++){ ind.se++; if(ind.se > n) ind.se = 1; if(inputSeq[i] <= n && inputSeq[i] != ind.se) return 0; } return 1; } int countReplacement(int N, int inputSeq[]){ int n = N; if(!val(n, inputSeq)) return 0; // cout << "OK\n"; // return 1; vector<int> vv; for(int i = 0; i < n; i++) if(inputSeq[i] > n) vv.pb(inputSeq[i]); // cout << vv.size() << "\n"; if(!vv.size()) return 1; sort(vv.begin(), vv.end()); int answer = 1; int lst = n; for(int i = 0; i < vv.size(); i++){ answer = ((ll)answer * (ll)binpw(vv.size() - i, vv[i] - lst - 1, mod + 2)) % (ll)(mod + 2); lst = vv[i]; // answer = (answer * ) } bool ck = 0; for(int i = 0; i < n; i++) ck |= (inputSeq[i] <= n); if(!ck) answer = ((ll)answer * (ll)n) % (mod + 2); return answer; } /* void process(){ int n; cin >> n; int arr[n], arr2[n]; for(int i = 0; i < n; i++) cin >> arr[i]; cout << countReplacement(n, arr) << "\n"; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) process(); } */

Compilation message (stderr)

gondola.cpp:19:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   19 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:34:15: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |  if(se.size() < n) return 0;
      |               ^
gondola.cpp: In function 'bool val(int, int*)':
gondola.cpp:123:15: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  123 |  if(se.size() < n) return 0;
      |               ^
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:160:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |  for(int i = 0; i < vv.size(); i++){
      |                 ~~^~~~~~~~~~~
#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...