Submission #815720

#	Time	Username	Problem	Language	Result	Execution time	Memory
815720		denniskim	Handcrafted Gift (IOI20_gift)	C++17	0 / 100	1 ms	212 KiB

gift

#include "gift.h"
#include <bits/stdc++.h>

using namespace std;
typedef int ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())

ll arr[500010];
ll num[500010];

int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x)
{
	string ans;
	vector<pll> vec;
	
	for(ll i = 0 ; i < n ; i++)
	{
		if(x[i] == 1)
			vec.push_back({a[i], b[i]});
	}
	
	if(vec.empty())
	{
		for(ll i = 0 ; i < n ; i++)
			ans.push_back('R');
		
		craft(ans);
		return 1;
	}
	
	sort(vec.begin(), vec.end());
	
	ll S = vec[0].fi;
	ll E = vec[0].se;
	ll cc = 1, cc2 = 1;
	
	for(auto &i : vec)
	{
		if(E < i.fi)
		{
			for(ll j = S ; j <= E ; j++)
				arr[j] = cc;
			
			cc++;
			S = i.fi, E = i.se;
		}
		
		else
			E = max(E, i.se);
	}
	
	for(ll j = S ; j <= E ; j++)
		arr[j] = cc;
	
	cc++;
	
	for(ll i = 0 ; i < n ; i++)
	{
		if(!arr[i])
			arr[i] = cc++;
	}
	
	for(ll i = 0 ; i < n ; i++)
	{
		if(!num[arr[i]])
			num[arr[i]] = cc2++;
	}
	
	for(ll i = 0 ; i < n ; i++)
	{
		if(x[i] == 2)
		{
			if(num[b[i]] - num[a[i]] == 0)
				return 0;
		}
	}
	
	char now = 'R';
	
	ans.push_back('R');
	
	for(ll i = 1 ; i < n ; i++)
	{
		if(arr[i] != arr[i - 1])
			now = 'B' + 'R' - now;
		
		ans.push_back(now);
	}
	
	craft(ans);
	return 1;
}

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