Submission #1228884

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228884		sleepntsheep	Handcrafted Gift (IOI20_gift)	C++20	100 / 100	901 ms	38584 KiB

gift

#include "gift.h"
#include <set>

using namespace std;

int construct(int n, int r, std::vector<int> a, std::vector<int> b, std::vector<int> x) {
	string ans(n, 'R');
	vector<int> a_(n);

	set<int> s;
	for (int i = 0; i < n; ++i)
		s.insert(i);

	for (int i = 0; i < r; ++i)
		if (x[i] == 1) {
			auto it = s.lower_bound(a[i]);
			if (it == s.end() || *it > a[i])
				--it;
			auto itr = s.upper_bound(b[i]);

			s.erase(next(it), itr);
		}

	for (int i = 0; i < r; ++i)
		if (x[i] == 2) {
			auto it = s.lower_bound(a[i]);
			if (it == s.end() || *it > a[i]) --it;
			auto it2 = s.lower_bound(b[i]);
			if (it2 == s.end() || *it2 > b[i])
				--it2;
			if (it == it2) {
				return 0;
			}
		}


	for (auto x : s) a_[x] ^= 1;
	for (int i = 0, run = 0; i < n; ++i) {
		run ^= a_[i];
		ans[i] = run ? 'R' : 'B';
	}

	craft(ans);
	return 1;
}

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