Submission #8900

#	Time	Username	Problem	Language	Result	Execution time	Memory
8900		pichulia	Gondola (IOI14_gondola)	C++98	40 / 100	20 ms	5972 KiB

gondola

#include<stdio.h>
#include<algorithm>
using namespace std;
#include"gondola.h"
#define M 1000000009
int n;
int a[100009];
int b[100009];
int x[100009];
int xl;
int y[300009];
int nono;
long long int res = 1;
int resb[300009];
int rl;
bool not_gon()
{
	int i, j;
	xl=0;
	for(i=0;i<n;i++)
		x[xl++] = a[i];
	for(i=0;i<n;i++)
	{
		if(a[i]<=n)
			break;
	}
	sort(x,x+xl);
	xl = unique(x,x+xl)-x;
	if(i==n) return xl<n;
    if(xl<n) return true;
	nono = 1;
	for(j=0;j<n;j++)
	{
		int k = (i+j)%n;
		if(a[k] > n || a[k] == (a[i] + j-1)%n+1) continue;
		return true;
	}
	return false;
}
long long int poww(long long p, long long q)
{
	long long int x,z;
	x=1;z=p;
	while(q)
	{
		if(q%2){x = (x*z)%M;}
		z= (z*z)%M;
		q/=2;
	}
	return x;
}
void process()
{
	int i, j, k;
	int save = n;
	int last;
	for(i=0;i<xl;i++)
		if(x[i] > n)
			break;
	save = n - i;
	last = n;
	res = 1;
	for(;i<xl;i++)
	{
		res = (res * poww(save,x[i] - last - 1))%M;
		save--;
		last = x[i];
	}
}
void process2()
{
	int i, j, k;
	int save = n;
	int last;
	for(i=0;i<xl;i++)
		if(x[i] > n)
			break;
	rl = 0;
	last = n;
	for(;i<xl;i++)
	{
		resb[rl++] = b[y[x[i]]];
		for(j=last+1;j<x[i];j++)
		{
			resb[rl++] = j;
		}
		last = x[i];
	}
}
int valid(int _n,int inputSeq[])
{
	int i, j, k;
	n = _n;
	for(i=0;i<n;i++)
		a[i] = inputSeq[i];
	if(not_gon())
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

int countReplacement(int _n, int inputSeq[])
{
	int i, j, k;
	n = _n;
	for(i=0;i<n;i++)
	{
		a[i] = inputSeq[i];
	}
  nono = 0;
	if(not_gon())
	{
		return 0;
	}
	else
	{
		if(nono==0)
		res = n;
		process();
		return res;
	}
}
int replacement(int _n, int gondolaSeq[], int replacementSeq[])
{
	int i, j, k;
	n = _n;
	for(i=0;i<n;i++)
		a[i] = gondolaSeq[i];
	process2();
	resb[rl] = 0;
	for(i=0;i<rl;i++)
		replacementSeq[i] = resb[i];
  return rl;

}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 0 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 20
• Subtask 7: 5 / 5
• Subtask 8: 15 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10