Submission #119637

#	Time	Username	Problem	Language	Result	Execution time	Memory
119637		Saboon	Library (JOI18_library)	C++14	100 / 100	352 ms	548 KiB

library

#include <bits/stdc++.h>
#include "library.h"

using namespace std;

vector<vector<int> > blocks;

int N;

int query(vector<int> t){
	vector<int> p(N);
	for (int i = 0; i < N; i++)
		p[i] = 0;
	for (auto it : t)
		p[it - 1] = 1;
	return Query(p);
}

int ask(int lo, int hi, int v){
	vector<int> t;
	for (int i = lo; i < hi; i++)
		for (auto it : blocks[i])
			t.push_back(it);
	t.push_back(v);
	return query(t);
}

void Solve(int n){
	N = n;
	int cnt = 0;
	for (int i = 1; i <= n; i++){
		cnt = blocks.size();
		if (ask(0, cnt, i) == cnt + 1)
			blocks.push_back({i});
		else{
			int lo = 0, hi = cnt;
			while (hi - lo > 1){
				int mid = (lo + hi) >> 1;
				if (ask(lo, mid, i) == (mid - lo + 1))
					lo = mid;
				else
					hi = mid;
			}
			int fi = lo;
			lo = 0, hi = cnt;
			while (hi - lo > 1){
				int mid = (lo + hi) >> 1;
				if (ask(mid, hi, i) == (hi - mid + 1))
					hi = mid;
				else
					lo = mid;
			}
			int se = lo;
			if (fi != se){
				if (blocks[fi].size() > 1 and query({blocks[fi][0], i}) == 1)
					reverse(blocks[fi].begin(), blocks[fi].end());
				if (blocks[se].size() > 1 and query({blocks[se].back(), i}) == 1)
					reverse(blocks[se].begin(), blocks[se].end());
				vector<int> q;
				for (auto it : blocks[fi])
					q.push_back(it);
				q.push_back(i);
				for (auto it : blocks[se])
					q.push_back(it);
				blocks.erase(blocks.begin() + se);
				blocks.erase(blocks.begin() + fi);
				blocks.push_back(q);
			}
			else{
				if (blocks[fi].size() == 1)
					blocks[fi].push_back(i);
				else{
					if (query({blocks[fi][0], i}) == 1)
						reverse(blocks[fi].begin(), blocks[fi].end());
					blocks[fi].push_back(i);
				}
			}
		}
/*		cout << "# " << i << " ------> \n";
		for (auto it : blocks){
			for (auto it2 : it)
				cout << it2 << " ";
			cout << '\n';
		}
*/	}
	Answer(blocks[0]);
}

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