#include <bits/stdc++.h>
#include "gondola.h"
#define F first
#define S second
using namespace std;
bool f[250003],F[250003];
int Gondol[250003];
pair < int , int > a[250003];
long long mod=1e9+9;
int valid(int n, int inputSeq[]) {
int idx=-1;
for (int i=0; i<n; i++)
if (!f[inputSeq[i]]) f[inputSeq[i]]=1;
else return 0;
for (int i=0; i<n; i++)
if (inputSeq[i]<=n) { idx=i; break; }
if (idx==-1) return 1;
int x=inputSeq[idx];
for (int i=idx+1; ; i++) {
x++;
if (x>n) x-=n;
if (i==n) i-=n;
if (i==idx) break;
if (inputSeq[i]<=n && inputSeq[i]!=x) return 0;
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
int l=0,M=0,idx=-1;
for (int i=0; i<n; i++)
if (gondolaSeq[i]<=n) { idx=i; break; }
for (int i=0; i<n; i++)
a[i].F=gondolaSeq[i],a[i].S=i;
sort(a,a+n);
if (idx==-1) {
for (int i=0; i<n; i++)
Gondol[i]=i+1;
}
else {
int x=gondolaSeq[idx];
Gondol[idx]=x;
for (int i=idx+1; ; i++) {
x++;
if (x>n) x-=n;
if (i==n) i-=n;
if (i==idx) break;
Gondol[i]=x;
}
}
int last=n;
for (int i=0; i<n; i++) {
if (a[i].F<=n) continue;
int id=a[i].S;
replacementSeq[l++]=Gondol[id];
for (int j=last+1; j<a[i].F; j++)
replacementSeq[l++]=j;
last=a[i].F;
}
return l;
}
long long po(long long a,long long b) {
long long res=1;
while (b>0) { if (b%2) res=(res*a)%mod; a=(a*a)%mod; b/=2; }
return res;
}
int countReplacement(int n, int inputSeq[]) {
if (!valid(n,inputSeq)) return 0;
sort(inputSeq,inputSeq+n);
long long ANS=1,last=n;
if (inputSeq[0]>n) ANS=(ANS*n)%mod;
for (int i=0; i<n; i++) {
if (inputSeq[i]<=n) continue;
ANS=(ANS*po(n-i,inputSeq[i]-last-1))%mod;
last=inputSeq[i];
}
return ANS;
}
Compilation message
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:34:10: warning: unused variable 'M' [-Wunused-variable]
int l=0,M=0,idx=-1;
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
380 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
7 ms |
764 KB |
Output is correct |
7 |
Correct |
13 ms |
1272 KB |
Output is correct |
8 |
Correct |
11 ms |
1020 KB |
Output is correct |
9 |
Correct |
5 ms |
504 KB |
Output is correct |
10 |
Correct |
13 ms |
1140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
6 ms |
760 KB |
Output is correct |
7 |
Correct |
13 ms |
1272 KB |
Output is correct |
8 |
Correct |
11 ms |
1016 KB |
Output is correct |
9 |
Correct |
5 ms |
504 KB |
Output is correct |
10 |
Correct |
12 ms |
1144 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
7 ms |
872 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
15 ms |
1304 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
400 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
424 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
348 KB |
Output is correct |
8 |
Correct |
3 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
408 KB |
Output is correct |
10 |
Correct |
3 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
380 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
3 ms |
380 KB |
Output is correct |
11 |
Correct |
15 ms |
2040 KB |
Output is correct |
12 |
Correct |
17 ms |
2168 KB |
Output is correct |
13 |
Correct |
19 ms |
1784 KB |
Output is correct |
14 |
Correct |
14 ms |
1912 KB |
Output is correct |
15 |
Correct |
23 ms |
2424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 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 |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
504 KB |
Output is correct |
7 |
Correct |
3 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
504 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
296 KB |
Output is correct |
9 |
Correct |
21 ms |
1244 KB |
Output is correct |
10 |
Correct |
17 ms |
1144 KB |
Output is correct |
11 |
Correct |
8 ms |
760 KB |
Output is correct |
12 |
Correct |
10 ms |
760 KB |
Output is correct |
13 |
Correct |
4 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
364 KB |
Output is correct |
6 |
Correct |
2 ms |
504 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
21 ms |
1356 KB |
Output is correct |
10 |
Correct |
17 ms |
1144 KB |
Output is correct |
11 |
Correct |
8 ms |
764 KB |
Output is correct |
12 |
Correct |
9 ms |
732 KB |
Output is correct |
13 |
Correct |
4 ms |
504 KB |
Output is correct |
14 |
Runtime error |
17 ms |
2040 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
15 |
Halted |
0 ms |
0 KB |
- |