Submission #836252

#	Time	Username	Problem	Language	Result	Execution time	Memory
836252		rainboy	Handcrafted Gift (IOI20_gift)	C++17	100 / 100	118 ms	22800 KiB

gift

#include "gift.h"
#include <cstring>
#include <string>
#include <vector>

using namespace std;

const int N = 500000;

typedef vector<int> vi;

int construct(int n, int m, vi ll, vi rr, vi kk) {
	static int dd[N];
	memset(dd, 0, n * sizeof *dd);
	for (int h = 0; h < m; h++)
		if (kk[h] == 1)
			dd[ll[h]]++, dd[rr[h]]--;
	for (int i = 1; i < n; i++)
		dd[i] += dd[i - 1];
	for (int i = n - 1; i > 0; i--)
		dd[i] = dd[i - 1] == 0 ? 1 : 0;
	dd[0] = 0;
	for (int i = 1; i < n; i++)
		dd[i] += dd[i - 1];
	for (int h = 0; h < m; h++)
		if (kk[h] == 2 && dd[rr[h]] - dd[ll[h]] == 0)
			return 0;
	string cc(n, 0);
	for (int i = 0; i < n; i++)
		cc[i] = dd[i] % 2 == 0 ? 'R' : 'B';
	craft(cc);
	return 1;
}

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