Submission #331138

#	Time	Username	Problem	Language	Result	Execution time	Memory
331138		pit4h	Library (JOI18_library)	C++14	100 / 100	495 ms	760 KiB

library

#include<bits/stdc++.h>
#include "library.h"
using namespace std;
using vi = vector<int>;

int n;

vector<vi> sub(vector<vi>& vec, int l, int r) {
	vector<vi> res;
	for(int i=l; i<=r; ++i) {
		res.push_back(vec[i]);
	}
	return res;
}

int qry(int x, int y) {
	vector<int> M(n);
	M[x-1] = M[y-1] = 1;
	return Query(M);
}
int qry(vi& v1, vi& v2) {
	vector<int> M(n);
	for(int i: v1) M[i-1] = 1;
	for(int i: v2) M[i-1] = 1;
	return Query(M);
}
int qry(vi v, vector<vi> V) {
	vector<int> M(n);
	for(int i: v) M[i-1] = 1;
	for(vi i: V) for(int j: i) M[j-1] = 1;
	return Query(M);
}
void rec(vi& v, vector<vi>& V, int l, int r) {
	if(l==r) {
		if(qry(v[0], V[l][0])==1) {
			reverse(v.begin(), v.end());
		}
		else if(qry(v.back(), V[l].back())==1) {
			reverse(V[l].begin(), V[l].end());
		}
		else if(qry(v[0], V[l].back())==1) {
			reverse(v.begin(), v.end());
			reverse(V[l].begin(), V[l].end());
		}
		for(int i: V[l]) v.push_back(i);
		V[l].clear();
		return;
	}

	int mid = (l+r)/2;
	if(qry(v, sub(V, l, mid)) <= mid-l+1) {
		rec(v, V, l, mid);
	}
	if(qry(v, sub(V, mid+1, r)) <= r-(mid+1)+1) {
		rec(v, V, mid+1, r);
	}
}
vector<vi> solve(vector<vi>& vec, int l, int r) {
	if(l==r) {
		return vector<vi>{vec[l]};
	}
	int mid = (l+r)/2;
	vector<vi> v1, v2;
	v1 = solve(vec, l, mid);
	v2 = solve(vec, mid+1, r);

	for(vi v: v1) {
		if(qry(v, v2) <= (int)v2.size()) {
			rec(v, v2, 0, (int)v2.size()-1);	
			vector<vi> new_v2;
			for(auto i: v2) {
				if(!i.empty()) new_v2.push_back(i);
			}
			v2 = new_v2;
		}
		v2.push_back(v);
	}
	/*cerr<<"solve("<<l<<' '<<r<<"): ";
	for(auto i: v2) {
		cerr<<"{";
		for(int j: i) {
			cerr<<j<<' ';
		}
		cerr<<"} ";
	}
	cerr<<'\n';*/
	return v2;
}
void Solve(int N)
{
	n = N;
	vector<vi> vec(N);
	for(int i=0; i<n; ++i) {
		vec[i].push_back(i+1);
	}
	random_shuffle(vec.begin(), vec.end());
	auto res = solve(vec, 0, n-1);
	/*cerr<<res.size()<<'\n';
	for(int i: res[0]) {
		cerr<<i<<' ';
	}
	cerr<<'\n';*/
	Answer(res.back());
}

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