제출 #374529

#제출 시각아이디문제언어결과실행 시간메모리
374529Aryan_Raina곤돌라 (IOI14_gondola)C++14
75 / 100
49 ms4612 KiB
#include "gondola.h" #include <bits/stdc++.h> using namespace std; #define ll long long const ll MOD = 1e9+9; int valid(int n, int a[]) { int rr = -1; set<int> vis; for (int i = 0; i < n; i++) { if (vis.count(a[i])) return 0; vis.insert(a[i]); if (a[i] <= n) { if (rr == -1) rr = i; if ((n + a[i] - a[rr]) % n != (n + i - rr) % n) return 0; } } return 1; } //---------------------- int replacement(int n, int a[], int replacementSeq[]) { int rr = -1; for (int i = 0; i < n; i++) { if (a[i] <= n) { rr = i; break; } } vector<array<int,2>> rep; for (int i = 0; i < n; i++) { if (a[i] > n) { int x = (a[rr] + i - rr + n) % n; if (x == 0) x = n; rep.push_back({a[i], x}); } } sort(rep.begin(), rep.end()); int ind = 0, last = n+1; for (int i = 0; i < rep.size(); ++i) { replacementSeq[ind++] = rep[i][1]; last++; for (; last <= rep[i][0]; ++last) replacementSeq[ind++] = last-1; } return ind; } //---------------------- ll modpow(ll a, ll b) { ll res = 1; while (b) { if (b & 1) res = (res * a)%MOD; a = (a * a)%MOD; b>>=1; } return res; } ll fact(ll a) { ll res = 1; for (int i = 1; i <= a; ++i) res = (res*i)%MOD; return res; } int countReplacement(int n, int a[]) { if (!valid(n, a)) return 0; vector<int> rep; for (int i = 0; i < n; i++) { if (a[i] > n) { rep.push_back(a[i]); } } sort(rep.begin(), rep.end()); ll ans = 1, last = n+1; int sz = rep.size(); for (int i = 0; i < sz; i++) { ans = (ans * modpow(sz-i, rep[i] - last)) % MOD; last = rep[i]+1; } if (rep.size() == n) { ans = (ans * fact(n)) % MOD; } return ans; }

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

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for (int i = 0; i < rep.size(); ++i) {
      |                  ~~^~~~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:83:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   83 |  if (rep.size() == 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...