이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "gondola.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pp pop_back
#define mp make_pair
#define bb back
#define ff first
#define ss second
using namespace std;
void rotatek(vector<int>& nums, int k) {
vector<int> cp = nums;
int n = nums.size();
for (int i = 0; i < n; i++)
nums[i] = cp[(i+k)%n];
}
int valid(int n, int inputSeq[])
{
vector<int> nums(n);
for (int i = 0; i < n; i++) nums[i] = inputSeq[i];
for (int i = 0; i < n; i++) {
if (nums[i] <= n) {
rotatek(nums, (i-nums[i]+1+n)%n);
break;
}
}
vector<int> rem;
for (int i = 0; i < n; i++) {
if (nums[i] <= n && nums[i] != i+1) return 0;
if (nums[i] > n) rem.pb(nums[i]);
}
sort(rem.begin(), rem.end());
for (int i = 1; i < rem.size(); i++) {
if (rem[i] != rem[i-1]+1) return 0;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
vector<int> nums(n);
vector<pair<int, int> > rem;
for (int i = 0; i < n; i++)
nums[i] = gondolaSeq[i];
for (int i = 0; i < n; i++) {
if (nums[i] <= n) {
rotatek(nums, (i-nums[i]+1+n)%n);
break;
}
}
for (int i = 0; i < n; i++) {
if (nums[i] > n) {
rem.pb({nums[i], i+1});
}
}
sort(rem.begin(), rem.end());
int now, next = n+1, ans = 0;
for (int i = 0; i < rem.size(); i++) {
now = rem[i].ss;
while (now < rem[i].ff) {
replacementSeq[ans] = now;
now = next, next++;
ans++;
}
}
return ans;
}
//----------------------
int modpow(int a, int b, int& MOD) {
if (b == 0) return 1;
int now = modpow(a, b/2, MOD);
if (b % 2) return ((now*now)%MOD*a)%MOD;
return (now*now)%MOD;
}
int countReplacement(int n, int inputSeq[])
{
int MOD = 1e9+9;
vector<int> nums(n), rem;
for (int i = 0; i < n; i++)
nums[i] = inputSeq[i];
for (int i = 0; i < n; i++) {
if (nums[i] <= n) {
rotatek(nums, (i-nums[i]+1+n)%n);
break;
}
}
int high = 1;
for (int i = 0; i < n; i++) {
if (nums[i] > n)
rem.pb(nums[i]);
else {
high = 0;
if (nums[i] != i+1)
return 0;
}
}
sort(rem.begin(), rem.end());
int now = n+1, ans = 1, mult = rem.size();
for (int i = 0; i < rem.size(); i++) {
ans = (ans*modpow(mult, rem[i]-now, MOD))%MOD;
now = rem[i]+1, mult--;
}
if (high)
ans = (ans*n)%MOD;
return ans;
}
/*
10
2
3 4
9
4
4 7 4 7
8
7
2 3 4 12 6 7 1
7
4
1 2 7 6
*/
컴파일 시 표준 에러 (stderr) 메시지
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:37:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for (int i = 1; i < rem.size(); i++) {
| ~~^~~~~~~~~~~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:68:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for (int i = 0; i < rem.size(); i++) {
| ~~^~~~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:116:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for (int i = 0; i < rem.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... |