# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
964309 | maxFedorchuk | Gondola (IOI14_gondola) | C++17 | 26 ms | 5124 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 <bits/stdc++.h>
using namespace std;
#include "gondola.h"
int valid(int n, int inputSeq[])
{
set < int > st;
int p=0;
for(int i=0;i<n;i++)
{
if(inputSeq[i]<=n)
{
p=(n+i-inputSeq[i])%n;
}
st.insert(inputSeq[i]);
}
if(st.size()!=n)
{
return 0;
}
for(int i=0;i<n;i++)
{
if(inputSeq[i]<=n)
{
if((n+i-inputSeq[i])%n!=p)
{
return 0;
}
}
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int ned_to_be[n],in=-1;
for(int i=0;i<n;i++)
{
if(gondolaSeq[i]<=n)
{
ned_to_be[i]=gondolaSeq[i];
in=i;
break;
}
}
if(in!=-1)
{
int nd=ned_to_be[in];
for(int i=(in+1)%n;i!=in;i=(i+1)%n)
{
nd%=n;
nd++;
ned_to_be[i]=nd;
}
}
else
{
for(int i=0;i<n;i++)
{
ned_to_be[i]=i+1;
}
}
map < int , int > mp;
int mx=0;
for(int i=0;i<n;i++)
{
if(gondolaSeq[i]>mx)
{
mx=gondolaSeq[i];
in=i;
}
if(gondolaSeq[i]>n)
{
mp[gondolaSeq[i]]=ned_to_be[i];
}
}
int uk=0;
for(int i=n+1;i<=mx;i++,uk++)
{
if(mp.find(i)==mp.end() || i==mx)
{
replacementSeq[uk]=ned_to_be[in];
ned_to_be[in]=i;
}
else
{
replacementSeq[uk]=mp[i];
}
}
return uk;
}
//----------------------
const long long MOD=1e9+7;
long long binpow(long long a,long long b)
{
long long rt=1;
while(b)
{
if(b&1)
{
rt=(rt*a)%MOD;
}
a=(a*a)%MOD;
b/=2;
}
return rt;
}
int countReplacement(int n, int inputSeq[])
{
if(!valid(n,inputSeq))
{
return 0;
}
set < long long > st;
for(long long i=0;i<n;i++)
{
if(inputSeq[i]>n)
{
st.insert(inputSeq[i]);
}
}
long long mun=n,ans=1,k=st.size();
for(auto u:st)
{
//cout<<u<<" "<<k<<" "<<u-mun-1<<"\n";
ans=(ans*binpow(k,u-mun-1))%MOD;
k--;
mun=u;
}
if(st.size()==n)
{
ans=(ans*n)%MOD;
}
return ans;
}
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... |