Cod sursa(job #784055)

Utilizator adascaluAlexandru Dascalu adascalu Data 4 septembrie 2012 20:53:34
Problema Reguli Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include<cstdio>
#include<vector>
#define MAXN 500000
using namespace std;
vector<long long >dif(MAXN);
int n;
FILE *g=fopen("reguli.out","w");
void prefix(int lg)
{
	vector<long long > a(MAXN),pi(MAXN),match(MAXN);
	int i,k=0,max=0;
	bool ok=true;
	for(i=1;i<=lg;++i)
		a[i]=dif[i];
	pi[1]=0;
	for(i=2;i<=lg;i++)
	{
		while(k && a[i]!=a[k+1])
			k=pi[k];
		if(a[i]==a[k+1])
			k++;
		pi[i]=k;
		
	}
	/*fprintf(g,"\n%u ",lg);
	for(i=1;i<=lg;i++)
		fprintf(g,"%lld ",pi[i]);*/
	for(i=1;pi[i]==0;i++)
		;
	max=i-1;
	for(;i<lg;i++)
		if(pi[i]>pi[i+1])
			ok=false;
	if(ok)
	{	
		fprintf(g,"%u\n",max);
		for(i=1;i<=max;i++)
			fprintf(g,"%lld\n",dif[i]);
	}
	else
	{
		fprintf(g,"%u\n ",lg);
		for(i=1;i<=lg;i++)
			fprintf(g,"%lld\n ",dif[i]);
	}
	/*return 1;
	k=0;

	for(i=1;i<=n;i++)
	{
		while(k && dif[i]!=a[k+1])
			k=pi[k];
		if(dif[i]==a[k+1])
			++k;
		match[i]=k;
		max=max<k ? k :max;
	}
	//fprintf(g,"\n");
	for(i=1;i<n;i++)
	{
	//	fprintf(g,"%lld\n",match[i]);
		if(!match[i])
			return 0;
	}
	for(i=2;i<n;i++)
	{
		if(match[i]!=match[i-1]+1 && match[i-1]!=max )
			return 0;
		else
			if(match[i-1]==max &&match[i]!=1)
				return 0;
	}
	return 1;*/
}
int main ()
{
	FILE * f=fopen("reguli.in","r");
	//FILE *g=fopen("reguli.out","w");
	fscanf(f,"%u",&n);
	long long x,y;
	int i;
	fscanf(f,"%lld",&x);
	for(i=1;i<=n;i++)
	{
		fscanf(f,"%lld",&y);
		dif[i]=y-x;
		x=y;
		//fprintf(g,"%lld  ",dif[i]);
	}
	//x=0
	//for(i=1;i<n && x;i++)
	//	x=(i);
	prefix(n-1);		
	/*fprintf(g,"%u\n",x);
	for(i=1;i<=x;i++)
		fprintf(g,"%lld\n",dif[i]);*/
	return 0;
}