#include "gondola.h"
#include <set>
#include <stdio.h>
#include <string.h>
#include <assert.h>
using namespace std;
int valid(int n, int inputSeq[])
{
set<int> st;
int num = -1;
for(int i = 0; i < n; i++)
{
st.insert(inputSeq[i]);
int idx = i%n;
if(inputSeq[idx] <= n && num == -1)
num = inputSeq[idx];
if(inputSeq[idx] <= n & num != inputSeq[idx])
return 0;
if(num != -1)
{
num++;
if(num == n+1)
num -= n;
}
}
return st.size() == n;
}
//----------------------
int A[500003];
int pos[500003];
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
memset(pos, -1, sizeof pos);
int mx = 0;
for(int i = 0; i < n; i++)
{
A[i] = gondolaSeq[i];
mx = max(mx, A[i]);
pos[A[i]] = i;
}
for(int i = 0; i < 3*n; i++)
{
if(A[(i-1+n)%n] <= n)
A[i%n] = A[(i-1+n)%n]+1;
if(A[i%n] == n+1) A[i%n] = 1;
}
if(A[0] > n)
{
for(int i = 0; i < n; i++)
{
A[i] = i+1;
}
}
// for(int i = 0; i < n; i++)
// printf("%d\n", A[i]);
int sz = 0;
for(int i = n+1; i <= mx; i++)
{
// printf("%d %d\n", i, pos[i]);
if(pos[i] == -1)
{
if(gondolaSeq[pos[mx]] == A[pos[mx]]) assert(0);
replacementSeq[sz++] = A[pos[mx]];
A[pos[mx]] = i;
}
else
{
if(gondolaSeq[pos[i]] == A[pos[i]]) assert(0);
replacementSeq[sz++] = A[pos[i]],
A[pos[i]] = i;
}
}
for(int i = 0; i < n; i++)
{
if(A[pos[gondolaSeq[i]]] < gondolaSeq[i])
assert(0);
}
for(int i = 0; i < n; i++)
{
// if(A[i] != gondolaSeq[i])
// printf("%d %d %d\n", i, A[i], gondolaSeq[i]);
}
// printf("\n");
return sz;
}
//----------------------
const long long MOD = 1e9+9;
bool ada[250003];
int countReplacement(int n, int inputSeq[])
{
if(!valid(n, inputSeq))
return 0;
long long res = 1;
long long hit = 0;
int mx = 0;
for(int i = 0; i < n; i++)
{
if(inputSeq[i] > n) hit++;
ada[inputSeq[i]] = 1;
mx = max(mx, inputSeq[i]);
}
// printf("%d\n", hit);
for(int i = n+1; i <= mx; i++)
{
printf("%d %d %lld\n", i, ada[i], hit);
if(ada[i])
hit--;
else
res = (res*hit)%MOD;
}
return res;
}
Compilation message
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:19:26: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
if(inputSeq[idx] <= n & num != inputSeq[idx])
~~~~~~~~~~~~~~^~~~
gondola.cpp:29:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
return st.size() == n;
~~~~~~~~~~^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
256 KB |
Output is correct |
6 |
Correct |
15 ms |
2296 KB |
Output is correct |
7 |
Correct |
13 ms |
636 KB |
Output is correct |
8 |
Correct |
27 ms |
3960 KB |
Output is correct |
9 |
Correct |
10 ms |
1400 KB |
Output is correct |
10 |
Correct |
35 ms |
4600 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
256 KB |
Output is correct |
6 |
Correct |
15 ms |
2168 KB |
Output is correct |
7 |
Correct |
13 ms |
632 KB |
Output is correct |
8 |
Correct |
28 ms |
3960 KB |
Output is correct |
9 |
Correct |
9 ms |
1528 KB |
Output is correct |
10 |
Correct |
34 ms |
4600 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
256 KB |
Output is correct |
13 |
Correct |
7 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
13 ms |
760 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
2296 KB |
Output is correct |
2 |
Correct |
4 ms |
2296 KB |
Output is correct |
3 |
Correct |
4 ms |
2296 KB |
Output is correct |
4 |
Correct |
3 ms |
2300 KB |
Output is correct |
5 |
Correct |
3 ms |
2296 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
2296 KB |
Output is correct |
2 |
Correct |
3 ms |
2296 KB |
Output is correct |
3 |
Correct |
4 ms |
2296 KB |
Output is correct |
4 |
Correct |
3 ms |
2296 KB |
Output is correct |
5 |
Correct |
4 ms |
2296 KB |
Output is correct |
6 |
Correct |
4 ms |
2296 KB |
Output is correct |
7 |
Correct |
4 ms |
2296 KB |
Output is correct |
8 |
Correct |
4 ms |
2296 KB |
Output is correct |
9 |
Correct |
4 ms |
2424 KB |
Output is correct |
10 |
Correct |
4 ms |
2296 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
2296 KB |
Output is correct |
2 |
Correct |
4 ms |
2296 KB |
Output is correct |
3 |
Correct |
4 ms |
2424 KB |
Output is correct |
4 |
Correct |
4 ms |
2296 KB |
Output is correct |
5 |
Correct |
3 ms |
2272 KB |
Output is correct |
6 |
Correct |
3 ms |
2296 KB |
Output is correct |
7 |
Correct |
4 ms |
2296 KB |
Output is correct |
8 |
Correct |
4 ms |
2296 KB |
Output is correct |
9 |
Correct |
4 ms |
2296 KB |
Output is correct |
10 |
Correct |
4 ms |
2296 KB |
Output is correct |
11 |
Correct |
15 ms |
2984 KB |
Output is correct |
12 |
Correct |
17 ms |
3044 KB |
Output is correct |
13 |
Correct |
17 ms |
3320 KB |
Output is correct |
14 |
Correct |
15 ms |
2808 KB |
Output is correct |
15 |
Correct |
24 ms |
4088 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
256 KB |
잘못된 접근입니다. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
256 KB |
잘못된 접근입니다. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
256 KB |
잘못된 접근입니다. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
256 KB |
잘못된 접근입니다. |
2 |
Halted |
0 ms |
0 KB |
- |