제출 #940621

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
940621		WonderfulWhale	도서관 (JOI18_library)	C++17	19 / 100	2123 ms	4160 KiB

library

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

#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int N;

vector<vector<int>> V;

bool f(vector<int> v, int X, int exl=-1) {
	vector<int> q(N, 0);
	q[X] = 1;
	bool skip = false;
	for(int x:v) {
		if(x==exl) {
			skip = true;
			continue;
		}
		for(int y:V[x])
			q[y] = 1;
	}
	//cerr << "we want to achieve: " << sz(v)-skip << "\n";
	return Query(q)<=sz(v)-skip;
}

int Find(vector<int> v, int X, int exl=-1) {
	cerr << "Find ";
	for(int x:v) cerr << x << " ";
	cerr << "\n";
	if(sz(v)==1)
		return v[0];
	vector<int> v1, v2;
	for(int i=0;i<sz(v);i++) {
		if(i%2==0) v1.pb(v[i]);
		else v2.pb(v[i]);
	}
	if(f(v1, X, exl)) {
		//cerr << "going v1\n";
		return Find(v1, X, exl);
	} else {
		//cerr << "going v2\n";
		return Find(v2, X, exl);
	}
}

void Solve(int n) {	
	N = n;
	V.pb({0});
	for(int i=1;i<n;i++) {
		vector<int> q(N, 0);
		for(auto x:V)
			for(auto y:x)
				q[y] = 1;
		q[i] = 1;
		int x = Query(q)-sz(V);
		if(x==1) {
			cerr << "new\n";
			V.pb({i});
		} else if(x==0) {
			cerr << "glue\n";
			vector<int> v(sz(V));
			iota(all(v), 0);
			int y = Find(v, i);
			vector<int> q1(N, 0);
			q1[i] = 1;
			q1[V[y][0]] = 1;
			if(Query(q1)==1) reverse(all(V[y]));
			V[y].pb(i);
		} else {
			cerr << "merge\n";
			vector<int> v(sz(V));
			iota(all(v), 0);
			int a = Find(v, i);
			cerr << "found: " << a << "\n";
			int b = Find(v, i, a);
			cerr << "found: " << b << "\n";
			vector<int> q1(N, 0);
			q1[i] = 1;
			q1[V[a][0]] = 1;
			if(Query(q1)==1) reverse(all(V[a]));
			vector<int> q2(N, 0);
			q2[i] = 1;
			q2[V[b].back()] = 1;
			if(Query(q2)==1) reverse(all(V[b]));
			V.emplace_back();
			for(int x:V[a]) V.back().pb(x);
			V.back().pb(i);
			for(int x:V[b]) V.back().pb(x);
			swap(V[a], V.back());
			V.pop_back();
			swap(V[b], V.back());
			V.pop_back();
		}
		cerr << "after---\n";
		for(auto x:V) {
			for(int y:x)
				cerr << y+1 << " ";
			cerr << "\n";
		}
		cerr << "---\n";
		
	}
	vector<int> res;
	for(int x:V[0])
		res.pb(x+1);
	Answer(res);
}

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