Submission #1222478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222478		poat	Library (JOI18_library)	C++17	100 / 100	72 ms	476 KiB

library

#include <bits/stdc++.h>
#include <cstdio>
#include <vector>
#include "library.h"
using namespace std;

mt19937 rng(time(0));


vector<int> f[1005];
set<pair<int, int>> S;

pair<int, int> getind(int ind)
{
	for(auto i : S)
	{
		ind--;
		if(ind == 0)
			return i;
	}
	assert(0);
}

int ask(int m, int x, int n)
{
	vector<int> v(n);
	
	v[x - 1] = 1;
	for(auto i : S)
	{
		m--;
		for(auto j : f[i.first])
			v[j - 1] = 1;

		if(m == 0)
			break;
	}

	return Query(v);
}
bool fask(int a, int b, int n)
{
	vector<int> v(n);
	v[a - 1] = 1;
	v[b - 1] = 1;
	return (Query(v) == 1);
}

void add(int ind, int x, int n)
{
	
	pair<int, int> p = getind(ind);

	S.erase(p);

	if(fask(p.second, x, n))
	{
		f[p.first].push_back(x);
		p.second = x;
	}
	else
	{
		f[x].push_back(x);
		for(auto i : f[p.first])
			f[x].push_back(i);
		f[p.first].clear();	
		p.first = x;
	}


	// cout << p.first << ' ' << p.second << ' ' << x << '\n';
	// exit(0);

	S.insert(p);
}


void Solve(int N)
{	
	for(int i = 0; i <= N; i++)
		f[i].clear();
	S.clear();


	vector<int> vec;
	for(int i = 1; i <= N; i++)
		vec.push_back(i);
	// shuffle(vec.begin(), vec.end(), rng);

	for(auto x : vec)
	{
		if(ask(S.size(), x, N) == S.size() + 1)
		{
			f[x].push_back(x);
			S.insert({x, x});
		}
		else if(ask(S.size(), x, N) == S.size())
		{
			int l = 0, r = S.size();
			while(r - l > 1)
			{
				int m = (l + r) / 2;
				if(ask(m, x, N) == m)
					r = m;
				else
					l = m;
			}
			add(r, x, N);
		}
		else if(ask(S.size(), x, N) == S.size() - 1)
		{
			int l = 0, r = S.size();
			while(r - l > 1)
			{
				int m = (l + r) / 2;
				if(ask(m, x, N) == m - 1)
					r = m;
				else
					l = m;
			}

			int i2 = r;

			l = 0, r--;
			while(r - l > 1)
			{
				int m = (l + r) / 2;
				if(ask(m, x, N) == m)
					r = m;
				else
					l = m;
			}
			int i1 = r;

			pair<int, int> p1 = getind(i1);
			pair<int, int> p2 = getind(i2);

			S.erase(p1);
			S.erase(p2);

			if(fask(x, p1.first, N))
			{
				f[p1.first].swap(f[p1.second]);
				swap(p1.first, p1.second);
				reverse(f[p1.first].begin(), f[p1.first].end());
			}

			if(fask(x, p2.second, N))
			{
				f[p2.first].swap(f[p2.second]);
				swap(p2.first, p2.second);
				reverse(f[p2.first].begin(), f[p2.first].end());
			}

			pair<int, int> p = {p1.first, p2.second};
			f[p1.first].push_back(x);
			for(auto i : f[p2.first])
				f[p1.first].push_back(i);
			f[p2.first].clear();

			S.insert(p);
		}
		else
			assert(0);
	}

	Answer(f[S.begin()->first]);
}

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