oj.uz

Submission #268185

# Submission time Handle Problem Language Result Execution time Memory
268185 2020-08-16T10:16:57 Z Shisuko Library (JOI18_library) C++14
100 / 100
 557 ms 592 KB 
#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

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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 384 KB # of queries: 2925
2 Correct 45 ms 384 KB # of queries: 2886
3 Correct 42 ms 396 KB # of queries: 3090
4 Correct 61 ms 384 KB # of queries: 3036
5 Correct 50 ms 288 KB # of queries: 3038
6 Correct 46 ms 384 KB # of queries: 3048
7 Correct 47 ms 384 KB # of queries: 3033
8 Correct 48 ms 384 KB # of queries: 2912
9 Correct 50 ms 384 KB # of queries: 3045
10 Correct 22 ms 416 KB # of queries: 1810
11 Correct 0 ms 256 KB # of queries: 0
12 Correct 1 ms 384 KB # of queries: 2
13 Correct 0 ms 256 KB # of queries: 5
14 Correct 1 ms 256 KB # of queries: 10
15 Correct 2 ms 384 KB # of queries: 112
16 Correct 4 ms 256 KB # of queries: 248

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 384 KB # of queries: 2925
2 Correct 45 ms 384 KB # of queries: 2886
3 Correct 42 ms 396 KB # of queries: 3090
4 Correct 61 ms 384 KB # of queries: 3036
5 Correct 50 ms 288 KB # of queries: 3038
6 Correct 46 ms 384 KB # of queries: 3048
7 Correct 47 ms 384 KB # of queries: 3033
8 Correct 48 ms 384 KB # of queries: 2912
9 Correct 50 ms 384 KB # of queries: 3045
10 Correct 22 ms 416 KB # of queries: 1810
11 Correct 0 ms 256 KB # of queries: 0
12 Correct 1 ms 384 KB # of queries: 2
13 Correct 0 ms 256 KB # of queries: 5
14 Correct 1 ms 256 KB # of queries: 10
15 Correct 2 ms 384 KB # of queries: 112
16 Correct 4 ms 256 KB # of queries: 248
17 Correct 539 ms 384 KB # of queries: 19877
18 Correct 540 ms 384 KB # of queries: 19658
19 Correct 544 ms 384 KB # of queries: 19997
20 Correct 498 ms 384 KB # of queries: 18623
21 Correct 443 ms 456 KB # of queries: 17508
22 Correct 550 ms 384 KB # of queries: 19920
23 Correct 557 ms 384 KB # of queries: 19916
24 Correct 187 ms 384 KB # of queries: 9248
25 Correct 506 ms 592 KB # of queries: 19434
26 Correct 474 ms 384 KB # of queries: 18237
27 Correct 207 ms 384 KB # of queries: 9179
28 Correct 315 ms 384 KB # of queries: 11963
29 Correct 310 ms 512 KB # of queries: 11950
30 Correct 302 ms 384 KB # of queries: 11963