Submission #434172

#	Time	Username	Problem	Language	Result	Execution time	Memory
434172		mosiashvililuka	Handcrafted Gift (IOI20_gift)	C++14	100 / 100	280 ms	32544 KiB

gift

#include "gift.h"
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,f[500009],NO,rg[500009],MX[500009];
string S;
pair <pair <int, int>, int> p[500009];
int construct(int Nn, int Rr, std::vector<int> Aa, std::vector<int> Bb, std::vector<int> Xx) {
	a=Nn;tes=Rr;
	for(t=1; t<=tes; t++){
		p[t].first.first=Aa[t-1]+1;p[t].first.second=Bb[t-1]+1;
		p[t].second=Xx[t-1];
	}
	for(i=1; i<=a; i++){
		f[i]=0;rg[i]=i;
	}
	sort(p+1,p+tes+1);
	zx=0;c=0;
	for(t=1; t<=tes; t++){
		if(p[t].second==2) continue;
		if(zx<p[t].first.first){
			c=p[t].first.first;zx=p[t].first.second;
		}else{
			zx=max(zx,p[t].first.second);
			rg[c]=zx;
		}
		rg[c]=zx;
	}
	i=1;j=0;
	while(i<=a){
		for(ii=i; ii<=rg[i]; ii++) f[ii]=j;
		j^=1;i=rg[i]+1;
	}
	for(i=2; i<=a; i++){
		if(f[i]!=f[i-1]){
			MX[i]=i-1;
		}else{
			MX[i]=MX[i-1];
		}
	}
	for(t=1; t<=tes; t++){
		if(p[t].second==1) continue;
		if(p[t].first.first==p[t].first.second){
			return 0;
		}
		if(MX[p[t].first.second]>=p[t].first.first){
			
		}else{
			return 0;
		}
	}
	for(i=1; i<=a; i++){
		if(f[i]==0){
			S+="R";
		}else{
			S+="B";
		}
	}
	craft(S);
	return 1;
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 25 / 25
• Subtask 5: 30 / 30