#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];
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;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
if (!valid(n,inputSeq)) return 0;
int k=0;
for (int i=0; i<n; i++)
if (inputSeq[i]>n) k++;
if (k<=1) return 1;
int idx=-1;
for (int i=0; i<n; i++)
if (inputSeq[i]<=n) { idx=i; break; }
sort(inputSeq,inputSeq+n);
long long mod=1e9+9,ANS=1,last=n;
for (int i=0; i<n; i++) {
if (inputSeq[i]<=n) continue;
ANS=(1LL*ANS*(inputSeq[i]-last))%mod;
last=inputSeq[i];
}
if (idx==-1) ANS=(ANS*n)%mod;
return ANS;
}
Compilation message
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:41: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 |
376 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 |
380 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
6 ms |
504 KB |
Output is correct |
7 |
Correct |
13 ms |
760 KB |
Output is correct |
8 |
Correct |
11 ms |
760 KB |
Output is correct |
9 |
Correct |
5 ms |
376 KB |
Output is correct |
10 |
Correct |
13 ms |
760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
380 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 |
380 KB |
Output is correct |
6 |
Correct |
6 ms |
504 KB |
Output is correct |
7 |
Correct |
13 ms |
760 KB |
Output is correct |
8 |
Correct |
11 ms |
632 KB |
Output is correct |
9 |
Correct |
5 ms |
508 KB |
Output is correct |
10 |
Correct |
12 ms |
760 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
380 KB |
Output is correct |
13 |
Correct |
7 ms |
632 KB |
Output is correct |
14 |
Correct |
2 ms |
380 KB |
Output is correct |
15 |
Correct |
15 ms |
760 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 |
3 ms |
376 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 |
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 |
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 |
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 |
376 KB |
Output is correct |
11 |
Correct |
14 ms |
1528 KB |
Output is correct |
12 |
Correct |
17 ms |
1784 KB |
Output is correct |
13 |
Correct |
17 ms |
1656 KB |
Output is correct |
14 |
Correct |
14 ms |
1528 KB |
Output is correct |
15 |
Correct |
23 ms |
2300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
380 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 |
256 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 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
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 |
376 KB |
Output is correct |
5 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |