Submission #1303564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303564		vtnoo	Gondola (IOI14_gondola)	C++20	100 / 100	43 ms	6092 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,pao=b;i<pao;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
int valid(int n, int a[])
{
    set<int>s;
    pair<int,int>p={1e9,1e9};
    fore(i,0,n){
        if(s.count(a[i]))return 0;
        s.insert(a[i]);
        if(a[i]<=n){
            p=min(p,{a[i],i});
        }
    }
    if(p.snd==1e9)return 1;
    int cur=p.fst+1;
    fore(i,p.snd+1,n){
		if(a[i]<=n&&a[i]!=cur)return 0;
		cur++;
	}
	fore(i,0,p.snd){
		if(a[i]<=n&&a[i]!=cur)return 0;
		cur++;
	}
	return 1;
}
int replacement(int n, int a[], int res[])
{
    int f=-1;
    fore(i,0,n){
        if(a[i]<=n){
            f=i;
            break;
        }
    }
    vector<pair<int,int>>t;
    if(f==-1){
        t.pb({1,a[0]});
        f=0;
        a[0]=1;
    }
    fore(i,f+1,n){
        if(a[i]>n){
            t.pb({a[(i-1+n)%n]%n+1,a[i]});
            a[i]=a[(i-1+n)%n]%n+1;
        }
    }
    fore(i,0,f){
        if(a[i]>n){
            t.pb({a[(i-1+n)%n]%n+1,a[i]});
            a[i]=a[(i-1+n)%n]%n+1;
        }
    }
    sort(ALL(t),[&](auto &a,auto &b){return a.snd<b.snd;});
    int cur=n+1,op=0;
    fore(i,0,SZ(t)){
        int ori=t[i].fst,tar=t[i].snd;
        while(ori<tar){
            res[op++]=ori;
            ori=cur++;
        }
    }
    return op;
}
const int MOD=1e9+9;
ll exp(ll a,ll b){
	if(b==0)return 1;
	ll tmp=exp(a,b/2);
	tmp*=tmp;
	tmp%=MOD;
	if(b%2)tmp*=a;
	tmp%=MOD;
	return tmp;
}
int countReplacement(int n, int a[])
{
	if(valid(n,a)==0)return 0;
	vector<int>v;
	fore(i,0,n){
		if(a[i]>n){
			v.pb(a[i]);
		}
	}
	sort(ALL(v));
	ll ans=1;
	int cur=n,tam=SZ(v);
	fore(i,0,SZ(v)){
		int diff=v[i]-cur-1;
		ans=(ans*exp(tam--,diff))%MOD;
		cur=v[i];
	}
	if(SZ(v)==n)ans*=n;
	ans%=MOD;
	return ans;
}  

• 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: 15 / 15
• Subtask 10: 10 / 10