Submission #434179

#	Time	Username	Problem	Language	Result	Execution time	Memory
434179		vanic	Handcrafted Gift (IOI20_gift)	C++14	100 / 100	203 ms	18908 KiB

gift

#include "gift.h"
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

const int maxn=5e5+5;
const string s="RB";


int pref[maxn];
int poz[maxn];
int neg[maxn];
string sol;

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){
			poz[a[i]]++;
			neg[b[i]+1]++;
		}
	}
	int sw=0;
	bool p=0;
	for(int i=0; i<n; i++){
		sw-=neg[i];
		if(!sw){
			p^=1;
		}
		sw+=poz[i];
		pref[i+1]=pref[i]+p;
		sol.push_back(s[p]);
	}
	for(int i=0; i<r; i++){
		if(x[i]==2 && (pref[b[i]+1]-pref[a[i]]==0 || pref[b[i]+1]-pref[a[i]]==b[i]-a[i]+1)){
			return 0;
		}
	}
	craft(sol);
	return 1;
}

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