# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
30312 | Nikefor | Gondola (IOI14_gondola) | C++98 | 19 ms | 3396 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "gondola.h"
#include <vector>
#include <algorithm>
#define mod 1000000009
using namespace std;
long long us(int x, int y) {
if(y==0) return 1;
if(y==1) return x%mod;
if(y&1) return (us(x,y>>1) + us(x, (y>>1)+1))%mod;
return (us(x, y>>1)*2)%mod;
}
int valid(int n, int inputSeq[])
{
vector<int> used;
for (int i = 0; i < n-1; ++i)
{
used.push_back(inputSeq[i]);
if(inputSeq[i]<=n and inputSeq[i+1]<=n and inputSeq[i+1]!=1 and inputSeq[i]>inputSeq[i+1]) return 0;
}
sort(used.begin(), used.end());
for(int i=0; i<used.size()-1; i++) if(used[i]==used[i+1]) return 0;
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
return -2;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
int res = 1, ctr=0;
if(!valid(n, inputSeq)) return -1;
bool flag = true;
vector<int> v;
for (int i = 0; i < n; ++i) {
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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |