Submission #483664

#	Time	Username	Problem	Language	Result	Execution time	Memory
483664		ymm	Library (JOI18_library)	C++17	100 / 100	329 ms	328 KiB

library

///
///   You fell for it, fool!
///   Thunder Cross Split Attack!
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
typedef long long ll;
using namespace std;

#include "library.h"

const int N = 1010;
int n;

vector<int> v;
int cnt[N];
int adj[N][2];
int mp[N];

int qry2(int x, vector<int>& v, int k)
{
	vector<int> kooft(n);
	Loop(i,0,k) kooft[v[i]] = 1;
	kooft[x] = 1;
	return Query(kooft);
}

int getsize(vector<int>& v, int k)
{
	int ans = k;
	Loop(i,0,k) Loop(j,i+1,k)
		if(adj[v[i]][0] == v[j] || adj[v[i]][1] == v[j])
			--ans;
	return ans;
}

void add(int x)
{
	cnt[x]++;
	v[x] = 1;
	vector<int> can;
	Loop(y,0,n) if(y != x && cnt[y] > 0 && cnt[y] < 3)
	{
		can.push_back(y);
	}
	for(int _ = 0; _ < 2 && can.size(); ++_)
	{
		int l = 0, r = can.size();
		if(qry2(x,can,r) > getsize(can,r)) break;
		while(r-l > 1)
		{
			int m = (l+r)/2;
			if(qry2(x,can,m) <= getsize(can,m)) r = m;
			else l = m;
		}
		int y = can[l];
		adj[y][cnt[y]++-1] = x;
		adj[x][cnt[x]++-1] = y;
		can.erase(can.begin()+l);
	}
}

void make(int v, int p, vector<int>& ans)
{
	ans.push_back(v+1);
	if(adj[v][0] == p)
		{if(cnt[v] == 3) make(adj[v][1], v, ans);}
	else
		make(adj[v][0], v, ans);
}

void Solve(int _n)
{
	n = _n;
	v.resize(n);
	if(n==1){v[0] = 1; Answer(v); return;}

	srand(time(0));
	vector<int> josuke(n);
	iota(josuke.begin(), josuke.end(), 0);
	random_shuffle(josuke.begin(),josuke.end());
	for(int x : josuke) add(x);

	vector<int> ans;
	Loop(i,0,n) if(cnt[i] == 2)
		{make(i,-1,ans); break;}
	Answer(ans);
}

• Subtask 1: 19 / 19
• Subtask 2: 81 / 81