Submission #707722

#	Time	Username	Problem	Language	Result	Execution time	Memory
707722		AdamGS	Handcrafted Gift (IOI20_gift)	C++17	100 / 100	161 ms	24952 KiB

gift

#include "gift.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=5e5+7;
int F[LIM], T[LIM];
int fnd(int x) {
	if(F[x]==x) return x;
	return F[x]=fnd(F[x]);
}
void uni(int a, int b) {
	F[fnd(b)]=fnd(a);
}
int construct(int n, int r, vector<int>a, vector<int>b, vector<int>x) {
	rep(i, n) T[i]=F[i]=i;
	rep(i, r) if(x[i]==1) T[a[i]]=max(T[a[i]], b[i]);
	rep(i, n) {
		if(i) T[i]=max(T[i], T[i-1]);
		if(T[i]>i) uni(i, i+1);
	}
	rep(i, r) if(x[i]==2 && fnd(a[i])==fnd(b[i])) return 0;
	int akt=0;
	string ans="";
	rep(i, n) {
		if(!akt) ans+="R"; else ans+="B";
		if(fnd(i)!=fnd(i+1)) akt^=1;
	}
	craft(ans);
	return 1;
}

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