제출 #754995

#제출 시각아이디문제언어결과실행 시간메모리
754995AngusRitossa곤돌라 (IOI14_gondola)C++14
100 / 100
43 ms6812 KiB
#include "gondola.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; #define mod 1000000009 int occurance[100010]; int exists[300010]; unordered_set<int> existsSET; int valid(int n, int inputSeq[]) { existsSET.clear(); for (int i = 0; i < n; i++) { if (inputSeq[i] <= n) { if (existsSET.find(inputSeq[i]) != existsSET.end()) return 0; occurance[inputSeq[i]] = i; existsSET.insert(inputSeq[i]); } else if (existsSET.find(inputSeq[i]) != existsSET.end()) return 0; else { existsSET.insert(inputSeq[i]); } } for (int i = 1; i <= n; i++) { if (existsSET.find(i) != existsSET.end()) { int loc = occurance[i]; for (int j = 1; j <= n; j++) { if (existsSET.find(j) != existsSET.end()) { int diff = occurance[j] + n - loc; diff %= n; int diff2 = j-i; if (diff != diff2) return 0; } } return 1; } } return 1; } //---------------------- int hasToDestroy[300010]; int replacement(int n, int gondolaSeq[], int replacementSeq[]) { fill_n(exists, 300010, 0); pair<int, int> mx = { 0, 0 }; int ans = 0; int firstloc = 1; for (int i = 0; i < n; i++) { exists[gondolaSeq[i]] = 1; occurance[gondolaSeq[i]] = i; mx = max(mx, { gondolaSeq[i], i } ); } for (int i = 1; i <= n; i++) { if (exists[i]) { firstloc = occurance[i]+1-i; firstloc += n; firstloc %= n; break; } } for (int i = 0; i < n; i++) { int initiallyhere = (i-firstloc+n)%n; initiallyhere++; if (gondolaSeq[i] != initiallyhere) hasToDestroy[gondolaSeq[i]] = initiallyhere; } int initialmx = (mx.second - firstloc +n)%n; initialmx++; exists[mx.first] = false; queue<int> q; q.push(initialmx); for (int i = n+1; i < mx.first; i++) { if (!exists[i]) q.push(i); } for (int i = n+1; i <= mx.first; i++) { if (!exists[i]) { replacementSeq[ans++] = q.front(); q.pop(); } else { replacementSeq[ans++] = hasToDestroy[i]; } } return ans; } ll pow(ll n, ll k) { if (k == 0) return 1; ll ans = pow(n, k/2); ans *= ans; ans %= mod; if (k % 2) ans *= n; return ans % mod; } //---------------------- int countReplacement(int n, int inputSeq[]) { if (!valid(n, inputSeq)) return 0; ll ans = 1; vector<int> v; ll pre = n; for (int i = 0; i < n; i++) { if (inputSeq[i] > n) v.push_back(inputSeq[i]); } sort(v.begin(), v.end()); reverse(v.begin(), v.end()); for (ll i = v.size()-1; i >= 0; i--) { ll at = v[i]; ll dist = at-pre-1; //printf("%lld %lld\n", at, dist); if (dist) { ll mult = pow((i+1),dist); //printf("%lld %lld %lld\n", at, dist, mult); mult %= mod; ans *= mult; ans %= mod; } pre = at; } if (v.size() == n) ans *= n; ans %= mod; return ans; }

컴파일 시 표준 에러 (stderr) 메시지

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:140:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  140 |  if (v.size() == n) ans *= n;
      |      ~~~~~~~~~^~~~
#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...