Submission #268185

#	Time	Username	Problem	Language	Result	Execution time	Memory
268185		Shisuko	Library (JOI18_library)	C++14	100 / 100	557 ms	592 KiB

library

#include <cstdio>
#include <chrono>
#include <random>
#include <algorithm>
#include <vector>
#include <iostream>
#include <map>
#include <set>
#include "library.h"
using namespace std;
struct EntityHandler
{
	mt19937 rng;

	int N;
	vector<vector<int>> segments;
	vector<int> M;
	int query(vector<int>& M)
	{
		return Query(M);
	}
	EntityHandler(int N):N(N)
	{
		rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());

		segments.resize(N);
		for(int g = 0; g < N; g++)
			segments[g] = {g};
	}
	void choose(vector<vector<int>> vv, vector<int>& M)
	{
		M = vector<int>(N,0);
		for(const auto& x : vv)
			for(const int& g : x)
				M[g] = 1;
	}
	void print(vector<int> x)
	{
		cout<<"{";
		for(const int& g : x)
			cout<<g+1<<(g==x.back() ? "}" : ",");
	}
	void merge(int x, int y)
	{
		if(segments[x].size() < segments[y].size())
			swap(segments[x],segments[y]);

		if(segments[y].size() > 1)
		{
			choose({segments[x],{segments[y][0]}},M);
			if(query(M)==2)
				reverse(segments[y].begin(),segments[y].end());
		}
		if(segments[x].size() > 1)
		{
			choose({{segments[x].back()},{segments[y][0]}}, M);
			if(query(M)==2)
				reverse(segments[x].begin(),segments[x].end());
		}
		segments[x].insert(segments[x].end(),segments[y].begin(),segments[y].end());
		swap(segments.back(),segments[y]);
		segments.pop_back();
	}
	int bs1() //least i s.t. set[0,i] has an adjacency
	{
		int L = 1;
		int R = segments.size()-1;
		while(R-L > 1)
		{
			int Mid = (L+R)/2;
			choose(vector<vector<int>>(segments.begin(),segments.begin()+Mid+1), M);
			if(query(M)!=Mid+1)
				R = Mid;
			else
				L = Mid;
		}
		for(int ans = L; ans <= R; ans++)
		{
			choose(vector<vector<int>>(segments.begin(),segments.begin()+ans+1), M);
			if(query(M)!=ans+1)
				return ans;
		}
		return -1;
	}
	int bs2(int i) //greatest j s.t. set[j,i] has an adjacency
	{
		int L = 0;
		int R = i-1;

		while(R-L > 1)
		{
			int Mid = (L+R)/2;
			choose(vector<vector<int>>(segments.begin()+Mid,segments.begin()+i+1), M);
			if(query(M)!=(i-Mid+1))
				L = Mid;
			else
				R = Mid;
		}
		for(int ans = R; ans >= L; ans--)
		{
			choose(vector<vector<int>>(segments.begin()+ans,segments.begin()+i+1), M);
			if(query(M)!=(i-ans+1))
				return ans;
		}
		return -1;
	}
	void merge()
	{
		int i, j;
		i = bs1();
		j = bs2(i);
		merge(j,i);
	}
	vector<int>& ans()
	{
		return segments[0];
	}
};
void Solve(int N)
{
	EntityHandler e(N);
	while(e.ans().size() < N)
		e.merge();

	vector<int> res = e.ans();
	for(int g = 0; g < N; g++)
		++res[g];
	Answer(res);
}

Compilation message (stderr)

library.cpp: In function 'void Solve(int)':
library.cpp:122:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  122 |  while(e.ans().size() < N)
      |        ~~~~~~~~~~~~~~~^~~

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