제출 #422334

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
422334		dreezy	곤돌라 (IOI14_gondola)	C++17	100 / 100	83 ms	6012 KiB

gondola

#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;

/**********************/
#define ll long long
const int mod = 1e9 + 9;
int valid(int n, int inputSeq[])
{
	
	
	set<int> vis;
	
	for(int i=0; i<n; i++){
		if(vis.find(inputSeq[i])!= vis.end()) {
			return false;
		}
			
		vis.insert(inputSeq[i]);
	}
	int preval = -1;
	for(int i =n -1; i>=0; i--){
		if(inputSeq[i] <=n){
			preval = (n - i) + inputSeq[i];
			if(preval> n) preval-=n;
			break;
		} 
			
	}
	
	if(preval == -1) return true;
	preval -=1;
	for(int i =0; i<n; i++){
		//cout << preval<<endl;		
		if(inputSeq[i] <=n){
			if(preval == n){
				if(inputSeq[i] != 1) return false;
			}
			else
				if(inputSeq[i]!= preval+1) return false;
			preval = inputSeq[i];
		}
		else{
			//replacement, num can be anything
			
			if(preval == n)
				preval = 1;
			else preval++;
		}
	}
	
	return true;
	
}

//----------------------

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	//debug second subtask, something weird is wrong but i am close
	
	int preval = -1;
	for(int i =n -1; i>=0; i--){
		if(gondolaSeq[i] <=n){
			preval = (n - i) + gondolaSeq[i];
			if(preval> n) preval-=n;
			break;
		} 

			
	}
	set<pair<int,int>> replace;
	
	if(preval == -1){
		//all of them were replaced
		for(int i =  0; i<n; i++){
			replace.insert({gondolaSeq[i], i+1});
		}
	}
	else{
		preval-=1;
		//cout << preval<<endl;
		
		
		for(int i =0; i<n; i++){

			if(gondolaSeq[i] <=n){
				preval = gondolaSeq[i];
			}
			else{
				//replacement, num can be anything
				
				if(preval == n){
					replace.insert({gondolaSeq[i], 1});
					preval = 1;
					
				}
				else {
					replace.insert({gondolaSeq[i], ++preval});
				}
				
			}
		}
	}
	
	int cnt = 0;
	int prev = n;
	for(pair<int,int> a : replace){
		//cout <<a.first<<", "<<a.second<<endl;
		replacementSeq[cnt] = a.second;
		cnt++;
		
		
		for(int i = prev+1; i< a.first; i++){
			replacementSeq[cnt] = i;
			cnt++;
			
		}
		
		prev =  a.first;
		
	}
	return cnt;
}

//----------------------
ll binexp(ll a, int b){
	if(b == 0) return 1;
	ll ans = binexp(a, b/2) % mod;
	
	if(b%2)
		return (ans * ans) %  mod * a % mod;
	else return ans * ans % mod;
}



int countReplacement(int n, int inputSeq[])
{
	
	if(!valid(n, inputSeq)) return 0;
 	int preval = -1;
	for(int i =n -1; i>=0; i--){
		if(inputSeq[i] <=n){
			preval = (n - i) + inputSeq[i];
			if(preval> n) preval-=n;
			break;
		} 

			
	}
	set<int> replace;
	
	if(preval == -1){
		//all of them were replaced
		for(int i =  0; i<n; i++){
			replace.insert(inputSeq[i]);
		}
	}
	else{
		preval-=1;
		//cout << preval<<endl;
		
		
		for(int i =0; i<n; i++){

			if(inputSeq[i] <=n){
				preval = inputSeq[i];
			}
			else{
				//replacement, num can be anything
				
				if(preval == n){
					replace.insert(inputSeq[i]);
					preval = 1;
					
				}
				else {
					++preval;
					replace.insert(inputSeq[i]);
				}
				
			}
		}
	}
	ll ans = 1;
	if(preval == -1)	ans = n;
	int prev = n+1;
	int cnt = 0;
	for( int a: replace){
		ans *= binexp((replace.size() - cnt), (a - prev)) ;
		ans%= mod;
		cnt++;
		prev = a+1;
		
		//cout << a<<": "<<ans<<endl;
	}
	
	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