Submission #422317

#	Time	Username	Problem	Language	Result	Execution time	Memory
422317		dreezy	Gondola (IOI14_gondola)	C++17	60 / 100	27 ms	2872 KiB

gondola

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

/**********************/
#define ll long long
const int mod = 1e9 + 7;
int valid(int n, int inputSeq[])
{
	
	
	vector<bool> vis(2.5e5, 0);
	
	for(int i=0; i<n; i++){
		if(vis[inputSeq[i]]) return false;
		vis[inputSeq[i]] = true;
	}
	
	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 exp(ll a, int b){
	ll ans = 1;
	for(int i = 0; i<b; i++)
		{
			ans *= a;
			ans%= mod;
		}
	return ans;
}

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;
	int prev = n+1;
	int cnt = 0;
	for( int a: replace){
		ans *= exp((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: 0 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10