Submission #153506

#	Time	Username	Problem	Language	Result	Execution time	Memory
153506		dennisstar	Gondola (IOI14_gondola)	C++11	75 / 100	24 ms	3320 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
int valid(int n, int inputSeq[])
{
	int i;
	int chk[250010];
	memset(chk, 0, sizeof(chk));
	for (i=0; i<n; i++) chk[inputSeq[i]]++;
	for (i=0; i<n; i++) if (chk[inputSeq[i]]!=1) return 0;
	for (i=0; i<n; i++) if (inputSeq[i]<=n) break;
	if (i>=n) return 1;
	int ar[100010];
	for (int j=0; j<n; j++) ar[(inputSeq[i]-1+j)%n]=inputSeq[(i+j)%n];
	for (i=0; i<n; i++) if (ar[i]<=n&&i+1!=ar[i]) return 0;
	return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	int chk[250010]; int i, j;
	int ar[100010];
	memset(chk, 0, sizeof(chk));
	int mx=0;
	for (i=0; i<n; i++) mx=max(mx, gondolaSeq[i]);
	for (i=0; i<n; i++) if (gondolaSeq[i]<=n) break;
	if (i<n) {
		for (j=0; j<n; j++) ar[(gondolaSeq[i]-1+j)%n]=gondolaSeq[(i+j)%n];
 		for (i=0; i<n; i++) gondolaSeq[i]=ar[i];
	}
	for (i=0; i<n; i++) chk[gondolaSeq[i]]=i+1;
	int fr=0;
	for (i=0; i<n; i++) ar[i]=i+1;
	for (i=n+1; i<=mx; i++) {
		if (chk[i]) {
			replacementSeq[i-n-1]=ar[chk[i]-1];
			ar[chk[i]-1]=i;
		}
		else {
			for (; ar[fr]==gondolaSeq[fr]; fr++) {}
			replacementSeq[i-n-1]=ar[fr];
			ar[fr]=i;
		}
	}
	return mx-n;
}

//----------------------
typedef long long ll;
const ll MAX=1000000009ll;
ll mypow(ll n, int k)
{
	if (n==0) return 1;
	if (k==0) return 1;
	ll ret=mypow(n,k/2);
	if (k%2) return ret*ret*n%MAX;
	else return ret*ret%MAX;
}

int countReplacement(int n, int gondolaSeq[])
{
	int chk[250010]; int i, j;
	

	memset(chk, 0, sizeof(chk));
	for (i=0; i<n; i++) chk[gondolaSeq[i]]++;
	for (i=0; i<n; i++) if (chk[gondolaSeq[i]]!=1) return 0;
	for (i=0; i<n; i++) if (gondolaSeq[i]<=n) break;
	if (i<n) {
		int arr[100010];
		for (j=0; j<n; j++) arr[(gondolaSeq[i]-1+j)%n]=gondolaSeq[(i+j)%n];
		for (i=0; i<n; i++) if (arr[i]<=n&&i+1!=arr[i]) return 0;
	}


	sort(gondolaSeq, gondolaSeq+n);
	long long ret=1, cnt=0;
	for (i=0; i<n; i++) if (gondolaSeq[i]>n) break;
	cnt=n-i;
	ret=mypow(cnt, gondolaSeq[i]-n-1);
	for (i=i+1; i<n; i++) {
		cnt--;
		ret=ret*mypow(cnt, gondolaSeq[i]-gondolaSeq[i-1]-1)%MAX;
	}
	return (int)ret;
}

• 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