제출 #1287999

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287999		Faisal_Saqib	곤돌라 (IOI14_gondola)	C++20	100 / 100	70 ms	10384 KiB

gondola

// #pragma once
#include "gondola.h"
#include <set>
#include <vector>
#include <algorithm>
#include <map>
#include <iostream>
using namespace std;
#define ll long long
ll powmod(ll a,ll b,ll mod)
{
	if(b==0)
		return 1;
	if(b==1)
		return a;
	ll h=powmod(a,b/2,mod);
	h=(h*h)%mod;
	if(b&1)
		h=(h*a)%mod;
	return h;
}
int valid(int n, int a[])
{
	int j=0;
	bool adspl=1;
	int val;
	for(int i=0;i<n;i++)
	{
		a[i]--;
		if(a[i]<=(n-1))
		{
			j=i;
			val=a[j];
			adspl=0;
		}
	}
	int level[n];
	int ok=j;
	set<int> spp;
	map<int,int> kidr;
	int mx=0;
	if(adspl)
		val=0;
	vector<int> nep;
	bool posas=1;
	for(int ap=0;ap<n;ap++)
	{
		level[j]=(val+ap)%n;
		if(level[j]!=a[j])
		{
			nep.push_back(a[j]);
			spp.insert(j);
			if(kidr.find(a[j])!=kidr.end())
			{
				posas=0;
			}
			kidr[a[j]]=j;
			if(a[j]<n)
			{
				posas=0;
			}
			mx=max(mx,a[j]);
		}
		j+=1;
		j%=n;
	}
	return posas;
	// sort(begin(nep),end(nep));
	// ll last=n;
	// for(int i=0;i<nep.size();i++)
	// {

	// }
	for(int ne=n;ne<=mx;ne++)
	{
		if(kidr.find(ne)==kidr.end())
		{
			level[*begin(spp)]=ne;
		}
		else
		{
			int f=kidr[ne];
			spp.erase(f);
		}
	}
	if(spp.size()==0)
		return 1;
	return 0;
}
int replacement(int n, int a[], int ans[])// Done
{
	int j=0;
	bool adspl=1;
	int val;
	for(int i=0;i<n;i++)
	{
		a[i]--;
		if(a[i]<=(n-1))
		{
			j=i;
			val=a[j];
			adspl=0;
		}
	}
	int level[n];
	int ok=j;
	set<int> spp;
	map<int,int> kidr;
	int mx=0;
	if(adspl)
		val=0;
	for(int ap=0;ap<n;ap++)
	{
		level[j]=(val+ap)%n;
		if(level[j]!=a[j])
		{
			spp.insert(j);
			kidr[a[j]]=j;
			mx=max(mx,a[j]);
		}
		j+=1;
		j%=n;
	}
	int l=0;
	for(int ne=n;ne<=mx;ne++)
	{
		if(kidr.find(ne)==kidr.end())
		{
			// Place some random place
			ans[l++]=level[*begin(spp)]+1;
			level[*begin(spp)]=ne;
		}
		else
		{
			int f=kidr[ne];
			spp.erase(f);
			ans[l++]=level[f]+1;
		}
	}
	return l;
}
int countReplacement(int n, int a[])
{
	if(!valid(n,a))
		return 0;
	ll ans=1,mod=1e9+9;
	int j=0;
	bool adspl=1;
	int val;
	int mx=0;
	for(int i=0;i<n;i++)
	{
		// a[i]--;
		mx=max(mx,a[i]);
		if(a[i]<=(n-1))
		{
			j=i;
			val=a[j];
			adspl=0;
		}
	}
	int ok=j,level=0;
	if(adspl)
	{
		val=0;
		ans=n;
	}
	vector<int> vape;
	for(int ap=0;ap<n;ap++)
	{
		level=(val+ap)%n;
		if(level!=a[j])
		{
			vape.push_back(a[j]);
			mx=max(mx,a[j]);
		}
		j+=1;
		j%=n;
	}
	sort(begin(vape),end(vape));
	ll last=n;
	ll top=vape.size();
	for(int i=0;i<vape.size();i++)
	{
		ll len=vape[i]-last;
		ans=(ans*powmod(top,len,mod))%mod;
		last=vape[i]+1;
		top--;
	}
	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