Submission #1218135

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218135		LeonidCuk	Gondola (IOI14_gondola)	C++20	60 / 100	32 ms	4680 KiB

gondola

#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
long long mod=1e9+7;
int valid(int n, int v[])
{
    map<int,int>mp;
    int k=1e9,x=-1;
    for(int i=0;i<n;i++)
    {
        if(mp[v[i]]==1)return 0;
        mp[v[i]]++;
        if(v[i]<k)
        {
            x=i;
            k=v[i];
        }
    }
    if(k>n)return 1;
    if(k==n)k=0;
    k++;
    int a=x;
    x=(x+1)%n;
    while(x!=a)
    {
        if(v[x]<=n&&v[x]!=k)return 0;
        x=(x+1)%n;
        if(k==n)k=0;
        k++;
    }
    return 1;
}
int replacement(int n, int v[], int res[])
{
    int k=1e9,x=-1;
    for(int i=0;i<n;i++)
    {
        if(v[i]<k)
        {
            x=i;
            k=v[i];
        }
    }
    vector<pair<int,int>>res1;
    if(k>n)
    {
        k=1;x=0;
        res1.push_back({v[0],1});
    }
    if(k==n)k=0;
    k++;
    int a=x;
    x=(x+1)%n;
    while(x!=a)
    {
        if(v[x]>n)
        {
            res1.push_back({v[x],k});
        }
        x=(x+1)%n;
        if(k==n)k=0;
        k++;
    }
    sort(res1.begin(),res1.end());
    int l=0;
    for(int i=0;i<res1.size();i++)
    {
        res[l]=res1[i].second;
        l++;
        if(i==0)a=n+1;
        else a=res1[i-1].first+1;
        for(int j=a;j<res1[i].first;j++)
        {
            res[l]=j;
            l++;
        }
    }
    return l;
}
long long vrni(long long a,long long b)
{
    long long res=1;
    for(int i=0;i<31;i++)
    {
        if(b&(1<<i))
        {
            res=(res*a)%mod;
        }
        a=(a*a)%mod;
    }
    return res;
}
int countReplacement(int n, int v[])
{
    if(valid(n,v)==0)return 0;
    vector<long long int>res1;
    long long int res=1;
    for(int i=0;i<n;i++)
    {
        if(v[i]>n)res1.push_back(v[i]);
    }
    sort(res1.begin(),res1.end());
    if(res1.size()==n)res=n;
    long long b=res1.size(),c;
    for(int i=0;i<res1.size();i++)
    {
        if(i==0)c=n+1;
        else c=res1[i-1]+1;
        res=(res*(vrni(b,res1[i]-c)))%mod;
        b--;
    }
    return res;
}

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