이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "gondola.h"
#include <numeric>
#include <algorithm>
#include <set>
#include <vector>
#include <iostream>
using namespace std;
using llong = long long;
#define BUGO(x) cerr << #x << " = " << x << '\n';
int valid(int n, int a[])
{
if (set<int>(a, a + n).size() != n) return false;
set<int> ones;
for (int i = 0; i < n; ++i)
if (a[i] <= n) {
int j = i - (a[i] - 1);
if (j < 0) j += n;
ones.insert(j);
}
return ones.size() <= 1;
}
//----------------------
int replacement(int n, int a[], int ans[])
{
int anslen = 0;
vector<int> must(n, -1);
for (int i = 0; i < n; ++i)
if (a[i] <= n) {
for (int j = i; j < i + n; ++j) {
must[j % n] = (a[i] + j - i) % n;
if (!must[j % n]) must[j % n] = n;
}
break;
}
if (must[0] == -1)
iota(must.begin(), must.end(), 1);
vector<int> inds; inds.reserve(n);
for (int i = 0; i < n; ++i)
if (a[i] > n)
inds.push_back(i);
auto comp = [&a](int l, int r) {
return a[l] < a[r];
};
sort(inds.begin(), inds.end(), comp);
int gondol = n + 1;
for (int i: inds)
while (must[i] < a[i]) {
ans[anslen++] = must[i];
must[i] = gondol++;
}
return anslen;
}
//----------------------
const llong mod = 1000'000'009LL;
llong binpow(llong a, llong p) {
if (p == 0) return 1;
if (p % 2) return (a * binpow(a, p - 1)) % mod;
return binpow((a * a) % mod, p / 2);
}
int countReplacement(int n, int a[])
{
if (!valid(n, a)) return 0;
vector<int> b; b.reserve(n);
for (int i = 0; i < n; ++i)
if (a[i] > n)
b.push_back(a[i]);
b.push_back(n);
sort(b.begin(), b.end());
llong ans = 1;
for (int i = 0; i + 1 < b.size(); ++i)
{
ans *= binpow((llong)b.size() - 1LL - i, b[i + 1] - b[i] - 1LL);
ans %= mod;
}
if (*min_element(a, a + n) > n)
{
throw;
for (llong i = 1; i <= n; ++i) {
ans *= i;
ans %= mod;
}
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:13:35: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
13 | if (set<int>(a, a + n).size() != n) return false;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:74:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for (int i = 0; i + 1 < b.size(); ++i)
| ~~~~~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |