# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1019322 |
2024-07-10T17:24:42 Z |
presko |
Gondola (IOI14_gondola) |
C++14 |
|
17 ms |
4560 KB |
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include "gondola.h"
#define MAXN 1000000010
#define MOD 1000000009
using namespace std;
bool used[MAXN];
int valid(int n, int inputSeq[])
{
for(long long i=0;i<n;i++)
{
if(used[inputSeq[i]])return 0;
used[inputSeq[i]]=1;
if(inputSeq[i]<=n)
{
long long prev=i-1,valp=inputSeq[i]-1;
if(prev<0)prev=n-1;
if(valp<1)valp=n;
long long next=i+1,valn=inputSeq[i]+1;
if(next>=n)next=0;
if(valn>n)valn=1;
if(inputSeq[prev]<=n && inputSeq[prev]!=valp)return 0;
if(inputSeq[next]<=n && inputSeq[next]!=valn)return 0;
}
}
return 1;
}
//----------------------
vector<pair<long long,long long>> order;
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
order.clear();
long long ans=0,pos=-1;
for(long long i=0;i<n;i++)if(gondolaSeq[i]<=n){pos=i;break;}
if(pos==-1)for(long long i=0;i<n;i++)order.push_back({gondolaSeq[i],i+1});
else
{
long long curr=gondolaSeq[pos];
for(long long i=pos-1;i>=0;i--)
{
curr--;
if(curr==0)curr=n;
if(gondolaSeq[i]>n)order.push_back({gondolaSeq[i],curr});
gondolaSeq[i]=curr;
}
for(long long i=n-1;i>pos;i--)
{
curr--;
if(curr==0)curr=n;
if(gondolaSeq[i]>n)order.push_back({gondolaSeq[i],curr});
gondolaSeq[i]=curr;
}
}
sort(order.begin(),order.end());
long long last=n;
for(long long i=0;i<(long long)order.size();i++)
{
long long ind=order[i].first;
long long frst=order[i].second;
replacementSeq[ans++]=frst;
for(long long j=last+2;j<=ind;j++)
{
replacementSeq[ans++]=j-1;
}
last=ind;
}
return ans;
}
//----------------------
long long power(long long x, long long n)
{
if(n==0)return 1;
if(n==1)return x;
long long half=power(x,n/2);
long long ne=(half*half)%MOD;
if(n&1){ne*=x;ne%=MOD;}
return ne%MOD;
}
int countReplacement(int n, int inputSeq[])
{
order.clear();
if(!valid(n,inputSeq))return 0;
long long pos=-1;
for(long long i=0;i<n;i++)if(inputSeq[i]<=n){pos=i;break;}
if(pos==-1)for(long long i=0;i<n;i++)order.push_back({inputSeq[i],i+1});
else
{
long long curr=inputSeq[pos];
for(long long i=pos-1;i>=0;i--)
{
curr--;
if(curr==0)curr=n;
if(inputSeq[i]>n)order.push_back({inputSeq[i],curr});
inputSeq[i]=curr;
}
for(long long i=n-1;i>pos;i--)
{
curr--;
if(curr==0)curr=n;
if(inputSeq[i]>n)order.push_back({inputSeq[i],curr});
inputSeq[i]=curr;
}
}
if(order.size()==0)return 1;
sort(order.begin(),order.end());
long long ans=1;
if(pos==-1)ans=n;
long long last=n;
for(long long i=0;i<(long long)order.size();i++)
{
long long ind=order[i].first;
long long use=power((long long)order.size()-i,ind-last-1)%MOD;
ans*=use;
ans%=MOD;
last=ind;
}
return (int)ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
2 ms |
604 KB |
Output is correct |
7 |
Correct |
5 ms |
748 KB |
Output is correct |
8 |
Correct |
4 ms |
604 KB |
Output is correct |
9 |
Correct |
2 ms |
348 KB |
Output is correct |
10 |
Correct |
5 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
2 ms |
604 KB |
Output is correct |
7 |
Correct |
6 ms |
604 KB |
Output is correct |
8 |
Correct |
5 ms |
732 KB |
Output is correct |
9 |
Correct |
2 ms |
344 KB |
Output is correct |
10 |
Correct |
5 ms |
604 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
2 ms |
604 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
9 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
600 KB |
Output is correct |
11 |
Correct |
5 ms |
604 KB |
Output is correct |
12 |
Correct |
5 ms |
604 KB |
Output is correct |
13 |
Correct |
9 ms |
1748 KB |
Output is correct |
14 |
Correct |
5 ms |
600 KB |
Output is correct |
15 |
Correct |
17 ms |
2576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
11 ms |
2004 KB |
Output is correct |
10 |
Correct |
9 ms |
1748 KB |
Output is correct |
11 |
Correct |
4 ms |
1240 KB |
Output is correct |
12 |
Correct |
5 ms |
1236 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
12 ms |
2004 KB |
Output is correct |
10 |
Correct |
9 ms |
1748 KB |
Output is correct |
11 |
Correct |
5 ms |
1236 KB |
Output is correct |
12 |
Correct |
5 ms |
1236 KB |
Output is correct |
13 |
Correct |
2 ms |
604 KB |
Output is correct |
14 |
Correct |
15 ms |
3624 KB |
Output is correct |
15 |
Correct |
17 ms |
4560 KB |
Output is correct |
16 |
Correct |
4 ms |
1276 KB |
Output is correct |
17 |
Correct |
11 ms |
3028 KB |
Output is correct |
18 |
Correct |
7 ms |
2260 KB |
Output is correct |