Submission #434174

#	Time	Username	Problem	Language	Result	Execution time	Memory
434174		vanic	Handcrafted Gift (IOI20_gift)	C++14	10 / 100	182 ms	16128 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";


bool 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){
			if(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: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 25
• Subtask 5: 0 / 30