Submission #903304

#	Time	Username	Problem	Language	Result	Execution time	Memory
903304		Jawad_Akbar_JJ	Gondola (IOI14_gondola)	C++17	75 / 100	48 ms	10304 KiB

gondola

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
 
#include "gondola.h"
 
using namespace std;
const int N = 1e5 + 10;
 
int valid(int n,int s[]){
	int mn = 2e9;
	int ss[n + n + 5] = {0};
 
	map<int,bool> seeen;
	
	for (int i=1;i<=n;i++)
		ss[i] = ss[i + n] = s[i-1];
 
	int ind = 0;
	for (int i=1;i<=n;i++){
		if (ss[i] <= n and ss[i] < mn)
			ind = i;
		mn = min(mn,ss[i]);
	}
 
	for (int i=1;i<=n;i++){
		if (seeen[ss[i]])
			return false;
		seeen[ss[i]] = true;
	}
 
	if (mn > n)
		return 1;
	
	if (ind < mn)
		ind += n;
	
	while (mn>1)
		ind--,mn--;
 
	for (int i=ind;mn<=n;mn++,i++)
		if (ss[i] != mn and ss[i] <= n)
			return 0;
	return 1;
}
 
int replacement(int n,int s[],int sss[]){
	int mn = n + 5;
	int ss[n + n + 5] = {0};
 
	for (int i=1;i<=n;i++)
		ss[i] = ss[i + n] = s[i-1];
 
	map<int,int> seen;
	int ind = 0;
	int mx = 0;
	for (int i=1;i<=n;i++){
		if (ss[i] <= n and ss[i] < mn)
			mn = min(mn,ss[i]),ind = i;
		mx = max(mx,ss[i]);
	}
 
	if (ind==0){
		int cur = 0;
		for (int i=1;i<=n;i++)
			seen[ss[i]] = i;
		
		for (int i=n+1;i<=mx;i++){
			if (seen[i]==0)
				sss[cur++] = seen[mx],seen[mx] = i;
			else
				sss[cur++] = seen[i];
		}
		return cur;
	}
 
 
	if (ind < mn)
		ind += n;
	
	while (mn>1)
		ind--,mn--;
 
	for (int i=ind ; mn<=n ; i++,mn++)
		seen[ss[i]] = mn;
	// 
	int cur = 0;
	for (int i=n+1;i<=mx;i++){
		// cout<<i<<" dd "<<seen[i]<<endl;
		if (seen[i]!=0)
			sss[cur++] = seen[i];
		else
			sss[cur++] = seen[mx],seen[mx] = i;
	}
 
	return cur;
}
 
 
long long power(int a,int b,long long m){
	if (b==0)
		return 1;
	if (b==1)
		return a;
	long long ans = power(a,b/2,m);
	ans = 1LL * ans * ans % m;
	if (b%2)
		ans = 1LL * a * ans % m;
	return ans % m;
}
 
 
int countReplacement(int n,int s[]){
	int mn = n + 5;
	int ss[n + 5] = {0};
 
	for (int i=1;i<=n;i++)
		ss[i] = s[i-1];
 
	int ind = 0;
	int mx = 0;
	
	for (int i=1;i<=n;i++)
		mx = max(mx,ss[i]);
	
	if (!valid(n,s))
		return 0;
	if (mx == n)
		return 1;
 
 
	vector<int> v;
	for (int i=1;i<=n;i++)
		if (ss[i] > n)
			v.push_back(ss[i]);
 
	v.push_back(n);
 
	sort(begin(v),end(v));
 
	int sz = v.size();
 
	long long ans = 1;
	long long mod = 1000000009;
 
	for (int i=1;i<sz;i++){
		int msng = v[i] - v[i-1] - 1;
		int rem = sz - i;
		ans = 1LL * ans * power(rem,msng,mod) % mod;
	}
	return ans % mod;
}

Compilation message (stderr)

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:115:6: warning: unused variable 'mn' [-Wunused-variable]
  115 |  int mn = n + 5;
      |      ^~
gondola.cpp:121:6: warning: unused variable 'ind' [-Wunused-variable]
  121 |  int ind = 0;
      |      ^~~

• 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: 0 / 15
• Subtask 10: 0 / 10