| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 794360 | medmdg | 곤돌라 (IOI14_gondola) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000010;
const int mod = 1000000009;
typedef pair<int, int> ii;
int modpow(int x, int y) {
if (y == 0) return 1;
if (y == 1) return x;
int ret = modpow(x, y / 2);
ret = 1LL * ret * ret % mod;
if (y % 2) ret = 1LL * ret * x % mod;
return ret;
}
int n;
int ar[MAXN];
set<int> there;
bool valid() {
ar[n] = ar[0];
for (int i = 0; i < n; i++) {
if (there.count(ar[i])) return false;
there.insert(ar[i]);
if (ar[i] < n && (ar[i + 1] != ar[i] + 1 && ar[i + 1] <= n)) {
return false;
}
if (ar[i] == n && (ar[i + 1] != 1 && ar[i + 1] <= n)) {
return false;
}
}
return true;
}
void replacement() {
vector<ii> repl;
bool fail = false;
do {
if (fail) {
repl.emplace_back(ar[0], 1);
ar[0] = 1;
}
for (int z = 0; z < 2 * n; z++) {
int i = z % n;
int j = (z + 1) % n;
if (ar[i] > n) continue;
if (ar[j] != ar[i] % n + 1) {
repl.emplace_back(ar[j], ar[i] % n + 1);
ar[j] = ar[i] % n + 1;
}
}
fail = ar[0] > n;
} while (fail);
sort(repl.begin(), repl.end());
int last = n + 1;
vector<int> ans;
for (int i = 0; i < repl.size(); i++) {
while (repl[i].second < repl[i].first) {
ans.push_back(repl[i].second);
repl[i].second = last++;
}
}
printf("%d", (int)ans.size());
for (int i = 0; i < ans.size(); i++) {
printf(" %d", ans[i]);
}
puts("");
}
int countReplacement() {
if (!valid()) return 0;
vector<int> big;
for (int i = 0; i < n; i++) {
if (ar[i] > n) {
big.push_back(ar[i]);
}
}
sort(big.begin(), big.end());
int ans = big.size() == n ? n : 1;
int gond = big.size();
int cur = n + 1;
for (int i = 0; i < big.size(); i++) {
int d = big[i] - cur;
ans = 1LL * ans * modpow(gond, d) % mod;
cur = big[i] + 1;
gond--;
}
return ans;
}