Submission #429095

#	Time	Username	Problem	Language	Result	Execution time	Memory
429095		charterla	Handcrafted Gift (IOI20_gift)	C++14	100 / 100	304 ms	27748 KiB

gift

#include "gift.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Range{
	int ls,rs,self;
}one[500005],two[500005];
int cn[2]={0,0};

bool cmp(Range a,Range b){
	return a.ls==b.ls?a.rs<b.rs:a.ls<b.ls;
}

bool tag[2000005];
bool check(int ls,int rs,int ld,int rd,int now){
	//cout<<ls<<","<<rs<<":"<<ld<<","<<rd<<"-->"<<now<<endl; 
	if(ls<=ld && rd<=rs)return tag[now];
	
	int mid=(ld+rd)/2;
	if(mid>=ls && !check(ls,rs,ld,mid,now<<1))return false;
	if(mid+1<=rs && !check(ls,rs,mid+1,rd,now<<1|1))return false;
	
	return true;
}

int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x) {
    for(int i=0;i<r;i++){
    	if(x[i]==1){
    		one[cn[0]].ls=a[i];
    		one[cn[0]].rs=b[i];
    		cn[0]++;
		}
		else{
			two[cn[1]].ls=a[i];
    		two[cn[1]].rs=b[i];
    		cn[1]++;
		}
	}
	
	sort(one,one+cn[0],cmp);
	for(int i=0;i<cn[0];i++)one[i].self=i;
	for(int i=1;i<cn[0];i++){
		int now=one[i].self,last=one[i-1].self;
		if(one[last].rs>=one[now].ls){
			one[last].ls=min(one[last].ls,one[now].ls);
			one[last].rs=max(one[last].rs,one[now].rs);
			one[now].self=last;
		}
	}
	//for(int i=0;i<cn[0];i++)cout<<one[i].self<<":"<<one[one[i].self].ls<<","<<one[one[i].self].rs<<" ";cout<<endl;
	
	int stn=1;
	while(stn<n)stn*=2;//cout<<stn<<endl;
	for(int i=0;i<stn+n;i++)tag[i]=false;
	for(int i=0;i<cn[0];i++){
		if(i==one[i].self){
			for(int j=one[i].ls+stn;j<=one[i].rs+stn;j++){
				tag[j]=true;
			}
		}
	}
	//for(int i=1;i<stn+n;i++)cout<<tag[i]<<" ";cout<<endl;
	for(int i=stn-1;i>=1;i--){
		if((i<<1)<stn+n){
			if((i<<1|1)<stn+n){
				tag[i]=tag[i<<1]&&tag[i<<1|1];
			}
			else{
				tag[i]=tag[i<<1];
			}
		}
	}
	//for(int i=1;i<stn+n;i++)cout<<tag[i]<<" ";cout<<endl;
	
	string ans="";char ch[2]={'R','B'};int temp=0;
	for(int i=stn;i<stn+n;i++){
		if(tag[i]==0 || (i>stn && tag[i]==1 && tag[i-1]==0))temp^=1;
		
		ans+=ch[temp];
	}//cout<<ans<<endl;
    
    for(int i=0;i<cn[1];i++){
    	if(two[i].rs-two[i].ls==0)return 0;
    	if(check(two[i].ls,two[i].rs,0,stn-1,1))return 0;
	}
    craft(ans);
    return 1;
}

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