이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
typedef long long ll;
int const N = 2.5e5 + 10;
int const MOD = 1e9 + 9;
constexpr ll pw(ll a, ll b, ll mod) {
return (!b ? 1 :
b & 1 ? a * pw(a * a % mod, b / 2, mod) % mod :
pw(a * a % mod, b / 2, mod));
}
int valid(int n, int inputSeq[]) {
int st = -1;
map<int, bool> mark;
for (int i = 0; i < n; i++) {
if (inputSeq[i] <= n) {
if (st == -1)
st = (inputSeq[i] - 1) - i + n;
else if (inputSeq[i] - 1 != (st + i) % n)
return 0;
}
if (mark[inputSeq[i]])
return 0;
mark[inputSeq[i]] = true;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
int st = 0, l = 0;
for (int i = 0; i < n; i++) {
if (gondolaSeq[i] <= n)
st = (gondolaSeq[i] - 1) - i + n;
l = max(l, gondolaSeq[i]);
}
vector<int> ind(l + 1, -1), tmp(n, 0);
for (int i = 0; i < n; i++) {
ind[gondolaSeq[i]] = i;
tmp[i] = 1 + (st + i) % n;
}
int ptr = 0;
for (int i = n + 1; i <= l; i++) {
while (ptr < n && tmp[ptr] == gondolaSeq[ptr])
ptr++;
int j = (ind[i] != -1 ? ind[i] : ptr);
replacementSeq[i - n - 1] = tmp[j];
tmp[j] = i;
}
return l - n;
}
//----------------------
int countReplacement(int n, int inputSeq[]) {
if (!valid(n, inputSeq))
return 0;
int l = *max_element(inputSeq, inputSeq + n);
set<int> st;
for (int i = 0; i < n; i++)
if (inputSeq[i] > n)
st.insert(inputSeq[i]);
int t = st.size(), last = n;
ll ans = 1;
for (int x : st) {
ans = ans * pw(t, x - last - 1, MOD) % MOD;
t--;
last = x;
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:63:9: warning: unused variable 'l' [-Wunused-variable]
63 | int l = *max_element(inputSeq, inputSeq + n);
| ^
# | 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... |