#include "gondola.h"
#include <vector>
#include <set>
#include <algorithm>
#include <cstdio>
#define mod 1000000009
using namespace std;
long long us(int x, int y) {
if(x==0) return 1;
if(y==0) return 1;
if(y==1) return x%mod;
long long a = us(x,y>>1);
if(y&1) return (a * a * x)%mod;
return (a*a)%mod;
}
int valid(int n, int inputSeq[])
{
set<int> used;
for(int i=0; i<n; i++) {
if(used.find(inputSeq[i])!= used.end()) return 0;
used.insert(inputSeq[i]);
}
int start = -1;
for (int i = 0; i < n; ++i) if(inputSeq[i]<=n) {start = i; break; }
if(start==-1) return 1;
int pos = start, next = inputSeq[start];
for(int i=0; i<n; i++) {
if(inputSeq[pos]<=n) {
if(inputSeq[pos]!=next) return 0;
}
pos++;
if(pos>=n) pos = 0;
next++;
if(next>=n) next = 1;
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
return -2;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
//for(int i=0 ; i<20; i++) printf("%d\n",us(2,i) );
int res = 1, ctr=0;
if(!valid(n, inputSeq)) return 0;
bool flag = true;
vector<int> v;
for (int i = 0; i < n; ++i) {
if(inputSeq[i]>n) flag = false;
if(i!=n-1 and inputSeq[i+1] != (inputSeq[i]+1) and inputSeq[i+1]!=1) flag = false;
if(inputSeq[i]>n) {
ctr++;
v.push_back(inputSeq[i]);
}
}
sort(v.begin(), v.end());
if(flag) return 1;
int last = n+1;
for(int i= 0; i<v.size(); i++) {
res*= us(v[i]-last, v.size()-i);;
last = v[i]+1;
}
return res;
}
Compilation message
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:68:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i= 0; i<v.size(); i++) {
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
2548 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
2548 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
2548 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
2548 KB |
Integer -2 violates the range [0, 350000] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
2548 KB |
Integer -2 violates the range [0, 350000] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
2548 KB |
Integer -2 violates the range [0, 350000] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
2548 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
2548 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
2548 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
2548 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |