Submission #599505

#	Time	Username	Problem	Language	Result	Execution time	Memory
599505		Bench0310	Gondola (IOI14_gondola)	C++17	75 / 100	42 ms	6612 KiB

gondola

#include <bits/stdc++.h>
#include "gondola.h"

using namespace std;
typedef long long ll;

int valid(int n,int inputSeq[])
{
    vector<int> v(n);
    for(int i=0;i<n;i++) v[i]=inputSeq[i];
    for(int i=0;i<n;i++)
    {
        if(v[i]<=n)
        {
            int one=(i-(v[i]-1)+n)%n;
            rotate(v.begin(),v.begin()+one,v.end());
            break;
        }
    }
    set<int> s;
    for(int i=0;i<n;i++)
    {
        if(s.find(v[i])!=s.end()) return 0;
        s.insert(v[i]);
        if(v[i]<=n&&v[i]!=i+1) return 0;
    }
    return 1;
}

int replacement(int n,int gondolaSeq[],int replacementSeq[])
{
    vector<int> v(n);
    for(int i=0;i<n;i++) v[i]=gondolaSeq[i];
    for(int i=0;i<n;i++)
    {
        if(v[i]<=n)
        {
            int one=(i-(v[i]-1)+n)%n;
            rotate(v.begin(),v.begin()+one,v.end());
            break;
        }
    }
    vector<int> trains[n];
    for(int i=0;i<n;i++) trains[i].push_back(i+1);
    int mx=0;
    for(int i=1;i<n;i++) if(v[i]>v[mx]) mx=i;
    vector<int> vis(v[mx]+1,0);
    for(int i=0;i<n;i++) vis[v[i]]=1;
    for(int i=n+1;i<=v[mx];i++) if(vis[i]==0) trains[mx].push_back(i);
    for(int i=0;i<n;i++) trains[i].push_back(v[i]);
    vector<int> res(v[mx]+1,0);
    for(int i=0;i<n;i++) for(int j=1;j<(int)trains[i].size();j++) res[trains[i][j]]=trains[i][j-1];
    for(int i=n+1;i<=v[mx];i++) replacementSeq[i-n-1]=res[i];
    return v[mx]-n;
}

int countReplacement(int n,int inputSeq[])
{
    if(valid(n,inputSeq)==0) return 0;
    const ll mod=1000000009;
    auto mul=[&](ll a,ll b)->ll{return (a*b)%mod;};
    auto fpow=[&](ll b,ll e)->ll
    {
        ll r=1;
        while(e)
        {
            if(e&1) r=mul(r,b);
            b=mul(b,b);
            e/=2;
        }
        return r;
    };
    vector<int> v={n};
    for(int i=0;i<n;i++) if(inputSeq[i]>=n+1) v.push_back(inputSeq[i]);
    sort(v.begin(),v.end());
    int sz=v.size();
    ll res=1;
    for(int i=1;i<sz;i++) res=mul(res,fpow(sz-i,v[i]-v[i-1]-1));
    return int(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: 15 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10