Cod sursa(job #784138)

Utilizator adascaluAlexandru Dascalu adascalu Data 4 septembrie 2012 23:24:33
Problema Reguli Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<cstdio>
#include<vector>
#define MAXN 500000
using namespace std;
vector<long long >dif(MAXN);
int n;
FILE *g=fopen("reguli.out","w");
vector<long long > pi(MAXN);
void prefix(int lg)
{
	int i,k=0;
	pi[1]=0;
	for(i=2;i<=lg;i++)
	{
		while(k && dif[i]!=dif[k+1])
			k=pi[k];
		if(dif[i]==dif[k+1])
			k++;
		pi[i]=k;
	}
}
int main ()
{
	FILE * f=fopen("reguli.in","r");
	//FILE *g=fopen("reguli.out","w");
	fscanf(f,"%u",&n);
	long long x,y;
	int i,lg;
	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);
	for(i=1;!pi[i];i++);
	lg=i-1;
	for(;i<n;i++)
		if(pi[i]%lg!=i%lg || !pi[i])
		{
			fprintf(g,"%u\n",n-1);
			for(i=1;i<n;i++)
				fprintf(g,"%lld\n",dif[i]);
			return 0;
		}
		
	fprintf(g,"%u\n",lg);
	for(i=1;i<=lg;i++)
		fprintf(g,"%lld\n",dif[i]);
	/*fprintf(g,"%u\n",x);
	for(i=1;i<=x;i++)
		fprintf(g,"%lld\n",dif[i]);*/
	return 0;
}