Cod sursa(job #2365046)

Utilizator patcasrarespatcas rares danut patcasrares Data 4 martie 2019 11:53:02
Problema Congr Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<unordered_map>
#define x first
#define y second
#define pb push_back
using namespace std;
ifstream fin("congr.in");
ofstream fout("congr.out");
const int DN=6e5+5;
int n,m,a[DN],sum,p[DN],lst[DN];
int main()
{
    fin>>n;
    m=n;
    n=2*n-1;
    for(int i=1;i<=n;i++)
    {
    	fin>>a[i];
    	a[i]%=m;
    	p[i]=i;
    }
    while(1)
    {
    	random_shuffle(p+1,p+n+1);
    	sum=0;
    	for(int i=0;i<=m;i++)
    		lst[i]=0;
    	for(int i=1;i<=n;i++)
    	{
    		sum=(sum+a[p[i]])%m;
    		if(i>=m)
    		{
    			sum=(sum+m-a[p[i-m+1]])%m;
    			lst[a[p[i-m+1]]]=p[i-m+1];
    		}
    		if(lst[(m-sum)%m]&&i>=m)
    		{
    			fout<<lst[(m-sum)%m]<<' ';
    			for(int j=i-m+2;j<=i;j++)
    				fout<<p[j]<<' ';
    			return 0;
    		}
    	}
    }
}