Submission #799050

#	Time	Username	Problem	Language	Result	Execution time	Memory
799050		FatihSolak	Gondola (IOI14_gondola)	C++17	100 / 100	52 ms	6516 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> get(int n,int inputSeq[]){
	int pos = 0;
	for(int i = 0;i<n;i++){
		if(inputSeq[i] <= n){
			pos = (i + 1 - inputSeq[i] + n)%n;
		}
	}
	vector<int> ret;
	for(int i = pos;i < n;i++){
		ret.push_back(inputSeq[i]);
	}
	for(int i = 0;i<pos;i++){
		ret.push_back(inputSeq[i]);
	}
	return ret;
}
int valid(int n, int inputSeq[]){
	vector<int> inp = get(n,inputSeq);
	set<int> s;
	for(int i = 0;i<n;i++){
		s.insert(inp[i]);
		if(inp[i] <= n && inp[i] != i + 1){
			return 0;
		}
	}
	if(s.size() != n)	
		return 0;
	return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[]){
	vector<int> inp = get(n,gondolaSeq);
	map<int,int> mp;
	int maxi = 0;
	for(int i = 0;i<n;i++){
		if(inp[i] > n){
			mp[inp[i]] = i;
			if(inp[maxi] < inp[i])
				maxi = i;
		}
	}
	int l = 0;
	int tmp = inp[maxi];
	inp[maxi] = maxi + 1;
	for(int i = n + 1;i <= tmp;i++){
		if(mp.count(i) && mp[i] != maxi){
			replacementSeq[l++] = mp[i] + 1;
		}
		else{
			replacementSeq[l++] = inp[maxi];
			inp[maxi] = i;
		}
	}
	return l;
}
//----------------------
const int mod = 1e9 + 9;
int binpow(int a,int b){
	int ret = 1;
	while(b){
		if(b & 1){
			ret = (long long)ret * a%mod;
		}
		a = (long long)a * a % mod;
		b >>= 1;
	}
	return ret;
}
int countReplacement(int n, int inputSeq[]){
	if(!valid(n,inputSeq)){
		return 0;
	}
	vector<int> inp = get(n,inputSeq);
	int ans = 1;
	bool ok = 1;
	set<int> s;
	for(int i = 0;i<n;i++){
		if(inp[i] <= n){
			ok = 0;
		}
		else s.insert(inp[i]);
	}
	if(ok){
		ans = (long long)ans * n % mod;
	}
	if(s.size()){
		int cnt = s.size();
		int last = n;
		for(auto u:s){
			ans = (long long)ans * binpow(cnt,u-last - 1)%mod;
			last = u;
			cnt--;
		}
	}
	return ans;
}

Compilation message (stderr)

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:29:14: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |  if(s.size() != n)
      |     ~~~~~~~~~^~~~

• 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