Submission #153517

#	Time	Username	Problem	Language	Result	Execution time	Memory
153517		dennisstar	Gondola (IOI14_gondola)	C++11	100 / 100	28 ms	3164 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;
	int i;
	ll ret=1;
	for (i=0; (1<<i)<=k; i++) {} i--;
	for (; i>=0; i--) {
		ret=ret*ret%MAX;
		if ((1<<i)&k) ret=ret*n%MAX;
	}
	return ret;
}

int arr[100010];
int countReplacement(int n, int gondolaSeq[])
{
	if (n==0) return 1;
	int i, j;

	for (i=0; i<n; i++) if (gondolaSeq[i]<=n) break;
	if (i<n) {
		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);
	for (i=0; i<n-1; i++) if (gondolaSeq[i]==gondolaSeq[i+1]) return 0;

	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);
	i++;
	for (; i<n; i++) {
		cnt--;
		if (cnt==0) assert(false);
		ret=ret*mypow(cnt, gondolaSeq[i]-gondolaSeq[i-1]-1)%MAX;
	}
	if (gondolaSeq[0]>n) return ret*n%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: 15 / 15
• Subtask 10: 10 / 10