#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
int valid(int n, int inputSeq[])
{
int i;
int chk[250010];
memset(chk, 0, sizeof(chk));
for (i=0; i<n; i++) chk[inputSeq[i]]++;
for (i=0; i<n; i++) if (chk[inputSeq[i]]!=1) return 0;
for (i=0; i<n; i++) if (inputSeq[i]<=n) break;
if (i>=n) return 1;
int ar[100010];
for (int j=0; j<n; j++) ar[(inputSeq[i]-1+j)%n]=inputSeq[(i+j)%n];
for (i=0; i<n; i++) if (ar[i]<=n&&i+1!=ar[i]) return 0;
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int chk[250010]; int i, j;
int ar[100010];
memset(chk, 0, sizeof(chk));
int mx=0;
for (i=0; i<n; i++) mx=max(mx, gondolaSeq[i]);
for (i=0; i<n; i++) if (gondolaSeq[i]<=n) break;
if (i<n) {
for (j=0; j<n; j++) ar[(gondolaSeq[i]-1+j)%n]=gondolaSeq[(i+j)%n];
for (i=0; i<n; i++) gondolaSeq[i]=ar[i];
}
for (i=0; i<n; i++) chk[gondolaSeq[i]]=i+1;
int fr=0;
for (i=0; i<n; i++) ar[i]=i+1;
for (i=n+1; i<=mx; i++) {
if (chk[i]) {
replacementSeq[i-n-1]=ar[chk[i]-1];
ar[chk[i]-1]=i;
}
else {
for (; ar[fr]==gondolaSeq[fr]; fr++) {}
replacementSeq[i-n-1]=ar[fr];
ar[fr]=i;
}
}
return mx-n;
}
//----------------------
int countReplacement(int n, int gondolaSeq[])
{
int chk[250010]; int i, j;
memset(chk, 0, sizeof(chk));
for (i=0; i<n; i++) chk[gondolaSeq[i]]++;
for (i=0; i<n; i++) if (chk[gondolaSeq[i]]!=1) return 0;
for (i=0; i<n; i++) if (gondolaSeq[i]<=n) break;
if (i<n) {
int arr[100010];
for (j=0; j<n; j++) arr[(gondolaSeq[i]-1+j)%n]=gondolaSeq[(i+j)%n];
for (i=0; i<n; i++) if (arr[i]<=n&&i+1!=arr[i]) return 0;
}
int ar[100010];
memset(chk, 0, sizeof(chk));
int mx=0;
for (i=0; i<n; i++) mx=max(mx, gondolaSeq[i]);
for (i=0; i<n; i++) if (gondolaSeq[i]<=n) break;
if (i<n) {
for (j=0; j<n; j++) ar[(gondolaSeq[i]-1+j)%n]=gondolaSeq[(i+j)%n];
for (i=0; i<n; i++) gondolaSeq[i]=ar[i];
}
for (i=0; i<n; i++) chk[gondolaSeq[i]]=i+1;
for (i=0; i<n; i++) ar[i]=i+1;
int cnt=0;
for (i=0; i<n; i++) if (gondolaSeq[i]>n) cnt++;
long long ret=1;
for (i=n+1; i<=mx; i++) {
if (!chk[i]) {
ret*=(long long)cnt; ret%=1000000009ll;
}
else cnt--;
}
return (int)ret;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1272 KB |
Output is correct |
2 |
Correct |
3 ms |
1244 KB |
Output is correct |
3 |
Correct |
3 ms |
1272 KB |
Output is correct |
4 |
Correct |
3 ms |
1272 KB |
Output is correct |
5 |
Correct |
3 ms |
1272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1272 KB |
Output is correct |
2 |
Correct |
3 ms |
1400 KB |
Output is correct |
3 |
Correct |
3 ms |
1272 KB |
Output is correct |
4 |
Correct |
3 ms |
1264 KB |
Output is correct |
5 |
Correct |
3 ms |
1272 KB |
Output is correct |
6 |
Correct |
8 ms |
1784 KB |
Output is correct |
7 |
Correct |
15 ms |
2168 KB |
Output is correct |
8 |
Correct |
12 ms |
2296 KB |
Output is correct |
9 |
Correct |
6 ms |
1656 KB |
Output is correct |
10 |
Correct |
14 ms |
2424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1296 KB |
Output is correct |
2 |
Correct |
3 ms |
1272 KB |
Output is correct |
3 |
Correct |
3 ms |
1272 KB |
Output is correct |
4 |
Correct |
3 ms |
1244 KB |
Output is correct |
5 |
Correct |
3 ms |
1272 KB |
Output is correct |
6 |
Correct |
8 ms |
1788 KB |
Output is correct |
7 |
Correct |
15 ms |
2120 KB |
Output is correct |
8 |
Correct |
12 ms |
2296 KB |
Output is correct |
9 |
Correct |
6 ms |
1576 KB |
Output is correct |
10 |
Correct |
16 ms |
2424 KB |
Output is correct |
11 |
Correct |
3 ms |
1272 KB |
Output is correct |
12 |
Correct |
3 ms |
1272 KB |
Output is correct |
13 |
Correct |
10 ms |
1788 KB |
Output is correct |
14 |
Correct |
3 ms |
1256 KB |
Output is correct |
15 |
Correct |
17 ms |
2424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1272 KB |
Output is correct |
2 |
Correct |
3 ms |
1272 KB |
Output is correct |
3 |
Correct |
3 ms |
1272 KB |
Output is correct |
4 |
Correct |
3 ms |
1272 KB |
Output is correct |
5 |
Correct |
3 ms |
1272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1272 KB |
Output is correct |
2 |
Correct |
3 ms |
1272 KB |
Output is correct |
3 |
Correct |
3 ms |
1276 KB |
Output is correct |
4 |
Correct |
3 ms |
1272 KB |
Output is correct |
5 |
Correct |
3 ms |
1272 KB |
Output is correct |
6 |
Correct |
3 ms |
1272 KB |
Output is correct |
7 |
Correct |
3 ms |
1272 KB |
Output is correct |
8 |
Correct |
3 ms |
1400 KB |
Output is correct |
9 |
Correct |
3 ms |
1272 KB |
Output is correct |
10 |
Correct |
4 ms |
1372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1420 KB |
Output is correct |
2 |
Correct |
3 ms |
1272 KB |
Output is correct |
3 |
Correct |
3 ms |
1272 KB |
Output is correct |
4 |
Correct |
3 ms |
1272 KB |
Output is correct |
5 |
Correct |
3 ms |
1260 KB |
Output is correct |
6 |
Correct |
3 ms |
1272 KB |
Output is correct |
7 |
Correct |
3 ms |
1372 KB |
Output is correct |
8 |
Correct |
3 ms |
1400 KB |
Output is correct |
9 |
Correct |
3 ms |
1272 KB |
Output is correct |
10 |
Correct |
3 ms |
1400 KB |
Output is correct |
11 |
Correct |
14 ms |
2296 KB |
Output is correct |
12 |
Correct |
15 ms |
2524 KB |
Output is correct |
13 |
Correct |
16 ms |
2412 KB |
Output is correct |
14 |
Correct |
14 ms |
2296 KB |
Output is correct |
15 |
Correct |
23 ms |
3248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1256 KB |
Output is correct |
2 |
Correct |
3 ms |
1272 KB |
Output is correct |
3 |
Correct |
3 ms |
1320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1272 KB |
Output is correct |
2 |
Correct |
3 ms |
1272 KB |
Output is correct |
3 |
Correct |
3 ms |
1272 KB |
Output is correct |
4 |
Correct |
3 ms |
1272 KB |
Output is correct |
5 |
Correct |
3 ms |
1272 KB |
Output is correct |
6 |
Correct |
3 ms |
1272 KB |
Output is correct |
7 |
Correct |
3 ms |
1272 KB |
Output is correct |
8 |
Correct |
3 ms |
1272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1272 KB |
Output is correct |
2 |
Correct |
3 ms |
1272 KB |
Output is correct |
3 |
Correct |
3 ms |
1276 KB |
Output is correct |
4 |
Correct |
3 ms |
1272 KB |
Output is correct |
5 |
Correct |
3 ms |
1272 KB |
Output is correct |
6 |
Correct |
3 ms |
1244 KB |
Output is correct |
7 |
Correct |
3 ms |
1272 KB |
Output is correct |
8 |
Correct |
3 ms |
1272 KB |
Output is correct |
9 |
Correct |
17 ms |
2296 KB |
Output is correct |
10 |
Correct |
12 ms |
2168 KB |
Output is correct |
11 |
Correct |
9 ms |
1656 KB |
Output is correct |
12 |
Correct |
9 ms |
1628 KB |
Output is correct |
13 |
Incorrect |
6 ms |
1400 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1272 KB |
Output is correct |
2 |
Correct |
3 ms |
1272 KB |
Output is correct |
3 |
Correct |
3 ms |
1272 KB |
Output is correct |
4 |
Correct |
3 ms |
1272 KB |
Output is correct |
5 |
Correct |
3 ms |
1276 KB |
Output is correct |
6 |
Correct |
3 ms |
1272 KB |
Output is correct |
7 |
Correct |
3 ms |
1272 KB |
Output is correct |
8 |
Correct |
3 ms |
1276 KB |
Output is correct |
9 |
Correct |
15 ms |
2424 KB |
Output is correct |
10 |
Correct |
15 ms |
2208 KB |
Output is correct |
11 |
Correct |
9 ms |
1660 KB |
Output is correct |
12 |
Correct |
9 ms |
1656 KB |
Output is correct |
13 |
Incorrect |
7 ms |
1404 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |