Submission #44669

#	Time	Username	Problem	Language	Result	Execution time	Memory
44669		PowerOfNinjaGo	Library (JOI18_library)	C++17	100 / 100	238 ms	724 KiB

library

#include <cstdio>
#include <vector>
#include <set>
#include "library.h"
#include <cstring>
#include <cassert>
#include <algorithm>
#ifdef atom
	#include "grader.cpp"
#endif
using namespace std;
struct cc
{
	vector<int> mem;
};
vector< cc > comps;
vector<int> input;
int n;
void clear()
{
	input.assign(n, 0);
}
void insert(cc x)
{
	for(auto k : x.mem) input[k-1] = 1;
}
int ask()
{
	return Query(input);
}
int dx(int from, int to, int work)
{
	int bf = to-from+1;
	clear();
	for(int i = from; i<= to; i++) insert(comps[i]);
	input[work-1] = 1;
	int res = ask();
	return res-bf;
}
void join(int index, int work)
{
	cc &here = comps[index];
	clear();
	input[here.mem[0]-1] = 1; input[work-1] = 1;
	int res = ask();
	if(res == 1)
	{
		//printf("this case\n");
		//work here
		here.mem.insert(here.mem.begin(), work);
	}
	else
	{
		//here work
		here.mem.push_back(work);
	}
}
void join2(int id1, int id2, int work)
{
	cc cc1 = comps[id1], cc2 = comps[id2];
	clear();
	input[cc1.mem[0]-1] = 1; input[work-1] = 1;
	int res = ask();
	clear();
	input[cc2.mem[0]-1] = 1; input[work-1] = 1;
	int res2 = ask();
	cc nouv; nouv.mem = cc1.mem;
	if(res == 1) reverse(nouv.mem.begin(), nouv.mem.end());
	nouv.mem.push_back(work);
	if(res2 == 1)
	{
		//1cc work cc2
		nouv.mem.insert(nouv.mem.end(), cc2.mem.begin(), cc2.mem.end());
	}
	else
	{
		//1cc work 2cc
		nouv.mem.insert(nouv.mem.end(), cc2.mem.rbegin(), cc2.mem.rend());
	}
	if(id1> id2) swap(id1, id2);
	comps.erase(comps.begin()+id2);
	comps.erase(comps.begin()+id1);
	comps.push_back(nouv);
}
int lookfor(int from, int to, int work)
{
	if(from == to) return from;
	int mid = (from+to)/2;
	int res = dx(from, mid, work);
	if(res == 0) return lookfor(from, mid, work);
	return lookfor(mid+1, to, work);
}
#define ii pair<int, int>
ii lookfor2(int from, int to, int work)
{
	if(from+1 == to) return ii(from, to);
	int mid = (from+to)/2;
	int res = dx(from, mid, work);
	if(res == -1) return lookfor2(from, mid, work);
	if(res == 0) return ii(lookfor(from, mid, work), lookfor(mid+1, to, work));
	return lookfor2(mid+1, to, work);
}
void Solve(int N)
{
	n = N;
	input.resize(N);
	cc one; one.mem.push_back(1);
	comps.push_back(one);
	for(int i = 2; i<= N; i++)
	{
		int res = dx(0, comps.size()-1, i);
		//printf("%d: %d\n", i, res);
		if(res == 1)
		{
			cc nouvelle; nouvelle.mem.push_back(i);
			comps.push_back(nouvelle);
			//printf("lone component %d\n", comps.size()-1);
		}
		else if(res == 0)
		{
			int k = lookfor(0, comps.size()-1, i);
			//printf("attach with %d\n", k);
			join(k, i);
		}
		else
		{
			ii tt = lookfor2(0, comps.size()-1, i);
			// printf("joined %d %d\n", tt.first, tt.second);
			join2(tt.first, tt.second, i);
		}
		//printf("now %d comps\n", comps.size());
		// for(int i = 0; i< (int) comps.size(); i++)
		// {
		// 	printf("comp %d: ", i);
		// 	for(auto x : comps[i].mem) printf("%d ", x);
		// 	printf("\n");
		// }
	}
	//for(int i = 1; i<= n; i++) printf("%d %d\n", lhs[i], rhs[i]);
	//for(auto x : res) printf("%d ", x);
	Answer(comps[0].mem);
}

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