Cod sursa(job #466710)

Utilizator cosmyoPaunel Cosmin cosmyo Data 27 iunie 2010 13:33:17
Problema Congr Scor 0
Compilator cpp Status done
Runda Stelele Informaticii 2010, clasele X-XII, Ziua 1 Marime 1.18 kb
#include<stdio.h>
#include<stdlib.h>
#include<map>
using namespace std;
long k,y[600005],x,sw,p,n,s[600005],a,b,w;
multimap<long,long> m;
int main()
{freopen("congr.in","r",stdin);
  scanf("%lld",&p);
   long i,j;
    for(i=1;i<=2*p-1;++i)
		{scanf("%lld",&x);
	     s[i]=(s[i-1]+x)%p;
		 y[i]=x%p;
		}
 fclose(stdin);
 sw=0;
 freopen("congr.out","w",stdout);
 for(i=0;i<=p-1;++i)
	 if(s[i+p]-s[i]==0)
	 {for(j=i+1;j<=i+p;++j)
		 printf("%lld ",j);
	  fclose(stdout);
	 exit(0);
	 }
 for(i=0;i<=p-1;++i)
    if(s[i+p]==s[i])
	{for(j=i+1;j<=i+p;++j)
      printf("%lld ",j);		
	 fclose(stdout);
	 exit(0);
	}
 for(i=1;i<=2*p-1;++i)
  m.insert(pair<long ,long>(s[i]%p,i));
 map<long,long>::iterator it;
 long q,l;
 for(i=1;i<=p;++i)
 {	it=m.find(s[i]);
    a=it->first;
	l=a;
     while(a==l)
	 {a=it->first;
	  ++it;
	  b=it->second;
	  l=it->first;
	  k=b-i;
	  q=0;
	
	  for(j=i+1;j<=b;++j)
		  if(k==p)
			  break;
		  else
		  if(y[j]==0)
				 --k,++q;
		  w=0;
		   
	  if(k==p)
		 { for(j=i+1;j<=b;++j)
			  if(y[j]==0&&w<q)
				  ++w;
			  else
				  printf("%ld ",j);
			exit(0);
		 }
		 

	 }		 
 }
 fclose(stdout);
 return 0;
}