제출 #815736

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
815736		denniskim	Handcrafted Gift (IOI20_gift)	C++17	15 / 100	107 ms	17000 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[5000010];
ll num[5000010];
string ans;
vector<pll> vec;

int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x)
{
	for(ll i = 0 ; i < n ; i++)
	{
		if(x[i] == 1)
			vec.push_back({b[i], a[i]});
	}
	
	ll cc = 1, cc2 = 1;
	ll gapa = 0;
	
	if(!vec.empty())
	{
		sort(vec.begin(), vec.end());
		
		ll S = vec[0].se;
		ll E = vec[0].fi;
		
		for(auto &i : vec)
		{
			if(!gapa)
			{
				gapa = 1;
				continue;
			}
			
			if(E < i.se)
			{
				for(ll j = S ; j <= E ; j++)
					arr[j] = cc;
				
				cc++;
				S = i.se, E = i.fi;
			}
			
			else
				E = max(E, i.fi);
		}
		
		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[arr[b[i]]] - num[arr[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: 15 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 25
• Subtask 5: 0 / 30