Submission #57592

#	Time	Username	Problem	Language	Result	Execution time	Memory
57592		vex	Gondola (IOI14_gondola)	C++14	65 / 100	32 ms	3812 KiB

gondola

#include<bits/stdc++.h>
#include<gondola.h>
#define maxn 250005
#define MOD 1000000009
#define pii pair<int,int>
using namespace std;
 
 
int b[maxn];
int valid(int n, int a[])
{
    int minn=0;
    for(int i=1;i<n;i++)if(a[i]<a[minn])minn=i;
 
    for(int i=0;i<n;i++)b[i]=a[(i+minn)%n];
    if(b[0]>n)return 1;
 
    sort(a,a+n);
    for(int i=0;i<n-1;i++)if(a[i]==a[i+1])return 0;
 
    int pre=0;
    for(int i=1;i<n;i++)
    {
        if(b[i]<=n)
        {
            if(b[i]-b[pre]!=i-pre)return 0;
            pre=i;
        }
    }
    return 1;
}
 
vector<pii>v;
int replacement(int n, int g[], int r[])
{
    if(!valid(n,g))return -1;
 
    int s=b[0];
    for(int i=0;i<n;i++)if(b[i]>n)
    {
        int br=(s+i)%n;if(br==0)br=n;
        v.push_back({b[i],br});
    }
    sort(v.begin(),v.end());
 
    int len=v.size();
    if(len==0)
    {
        return 0;
    }
 
  	int duz=0;
    for(int i=0;i<len;i++)
    {
        r[duz]=v[i].second;duz++;
        int pre=n;
        if(i!=0)pre=v[i-1].first;
 
        for(int j=pre+1;j<v[i].first;j++)
        {
          r[duz]=j;
          duz++;
        }
    }
  	return v[len-1].first-n;
}
 
long long ste(int x,int y)
{
    if(y==0)return 1;
    if(y%2==1)return (ste(x,y-1)*x)%MOD;
 
    long long res=ste(x,y/2);
    return (res*res)%MOD;
}
 
vector<int>br;
int countReplacement(int n, int a[])
{
    if(!valid(n,a))return 0;
 
    for(int i=0;i<n;i++)if(b[i]>n)br.push_back(b[i]);
    sort(br.begin(),br.end());
 
    long long sol=1;
    int len=br.size();
    for(int i=0;i<len;i++)
    {
        int pre=n;
        if(i!=0)pre=br[i-1];
        sol*=ste(len-i,br[i]-pre-1);
      	sol%=MOD;
    }
    return sol;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 20 / 20
• Subtask 7: 5 / 5
• Subtask 8: 15 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10