Submission #44666

#	Time	Username	Problem	Language	Result	Execution time	Memory
44666		PowerOfNinjaGo	Library (JOI18_library)	C++17	0 / 100	17 ms	308 KiB

library

#include <cstdio>
#include <vector>
#include <set>
#include "library.h"
#include <cstring>
#ifdef atom
	#include "grader.cpp"
#endif
using namespace std;
struct cc
{
	int left, right;
	set<int> mem;
};
vector< cc > comps;
vector<int> input;
int lhs[1005], rhs[1005];
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.left-1] = 1; input[work-1] = 1;
	int res = ask();
	//printf("joining %d and %d\n", index, work);
	if(res == 1)
	{
		//printf("this case\n");
		//work here.left
		rhs[work] = here.left, lhs[here.left] = work;
		here.left = work;
	}
	else
	{
		//here.right work
		lhs[work] = here.right, rhs[here.right] = work;
		here.right = work;
	}
	here.mem.insert(work);
}
void join2(int id1, int id2, int work)
{
	if(id1> id2) swap(id1, id2);
	cc cc1 = comps[id1], cc2 = comps[id2];
	clear();
	input[cc1.left-1] = 1; input[work-1] = 1;
	int res = ask();
	cc nouv;
	for(auto x : cc1.mem) nouv.mem.insert(x);
	for(auto x : cc2.mem) nouv.mem.insert(x);
	nouv.mem.insert(work);
	if(res == 1)
	{
		//cc2 work cc1
		rhs[cc2.right] = work; lhs[cc1.left] = work;
		lhs[work] = cc2.right; rhs[work] = cc1.left;
		nouv.left = cc2.left; nouv.right = cc1.right;
	}
	else
	{
		//cc1 work cc2
		rhs[cc1.right] = work; lhs[cc2.left] = work;
		lhs[work] = cc1.right; rhs[work] = cc2.left;
		nouv.left = cc1.left; nouv.right = cc2.right;
	}
	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);
	memset(lhs, -1, sizeof lhs); memset(rhs, -1, sizeof rhs);
	cc one; one.left = one.right = 1; one.mem.insert(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.left = nouvelle.right = i; nouvelle.mem.insert(i);
			comps.push_back(nouvelle);
		}
		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 = 1; i<= n; i++) printf("%d %d\n", lhs[i], rhs[i]);
	int st = -1;
	for(int i = 1; i<= n; i++) if(lhs[i] == -1) st = i;
	vector<int> res;
	while(st != -1)
	{
		res.push_back(st);
		st = rhs[st];
	}
	//for(auto x : res) printf("%d ", x);
	Answer(res);
}

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