oj.uz

Submission #422334

# Submission time Handle Problem Language Result Execution time Memory
422334 2021-06-10T03:28:18 Z dreezy Gondola (IOI14_gondola) C++17
100 / 100
 83 ms 6012 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 15 ms 2124 KB Output is correct
7 Correct 11 ms 552 KB Output is correct
8 Correct 31 ms 3896 KB Output is correct
9 Correct 9 ms 1356 KB Output is correct
10 Correct 36 ms 4392 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 15 ms 2124 KB Output is correct
7 Correct 10 ms 588 KB Output is correct
8 Correct 31 ms 3844 KB Output is correct
9 Correct 9 ms 1384 KB Output is correct
10 Correct 36 ms 4488 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 17 ms 2004 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 51 ms 4556 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 9 ms 580 KB Output is correct
12 Correct 11 ms 600 KB Output is correct
13 Correct 22 ms 2508 KB Output is correct
14 Correct 9 ms 588 KB Output is correct
15 Correct 26 ms 2804 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 56 ms 3908 KB Output is correct
10 Correct 47 ms 3384 KB Output is correct
11 Correct 16 ms 1436 KB Output is correct
12 Correct 20 ms 1688 KB Output is correct
13 Correct 4 ms 588 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 68 ms 3932 KB Output is correct
10 Correct 46 ms 3380 KB Output is correct
11 Correct 16 ms 1356 KB Output is correct
12 Correct 20 ms 1612 KB Output is correct
13 Correct 4 ms 588 KB Output is correct
14 Correct 74 ms 4420 KB Output is correct
15 Correct 83 ms 6012 KB Output is correct
16 Correct 13 ms 1348 KB Output is correct
17 Correct 54 ms 4140 KB Output is correct
18 Correct 28 ms 2380 KB Output is correct