제출 #1225547

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1225547		mychecksedad	도서관 (JOI18_library)	C++20	100 / 100	141 ms	592 KiB

library

#include "library.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;
using namespace std;


int query(vi x){
	int num = 0;
	for(int i = 0; i < x.size(); ++i) num += x[i] != 0;
	if(num == 0) return 0;
	return Query(x);
}

void Solve(int n)
{
	vector<int> X(n);
	if(n == 1){
		Answer(vi{1});
		return;
	}

	vector<vi> has(n);
	vector<vi> g(n);
	vector<vi> has2(n);
	vi go(n, -1);
	vi done(n, 0);
	for(int rep = 0; rep < 2; ++rep){
		for(int i = 0; i < n; ++i){
			int l = 0, r = n - 1, fine = -1;
			if(has[i].size() + has2[i].size() == 2 || done[i]) continue;
			while(l <= r){
				int mid = l+r>>1;
				for(int j = 0; j < n; ++j) X[j] = (j <= mid ? 1 : 0);
				for(int y: has[i]) X[y] = 0;
				for(int y: has2[i]) X[y] = 0;
				X[i] = 0;
				int num = query(X);
				X[i] = 1;
				int num2 = query(X);
				if(num + 1 != num2){
					fine = mid;
					r = mid - 1;
				}else{
					l = mid + 1;
				}
			}
			if(fine == -1){
				done[i] = 1;
				continue;
			}
		// cerr <<  i + 1 << ' ' << fine + 1 << '\n';
			go[i] = fine;
			g[go[i]].pb(i);
			g[i].pb(go[i]);
			has[go[i]].pb(i);
			has2[i].pb(go[i]);
		}
	}

	for(int i = 1; i <= n; ++i){
		assert(g[i-1].size());
		assert(g[i-1].size() < 3);
	}

	int root = 0;
	for(int i = 0; i < n; ++i) if(g[i].size() == 1) root = i;
	int v = root;
	
	vi res;
	res.pb(root);
	int last = -1;
	for(int i = 1; i < n; ++i){
		if(g[v][0] == last){
			last = v;
			v = g[v][1];
		}else{
			last = v;
			v = g[v][0];
		}
		res.pb(v);
	}
	// for(int x: res) cerr << x + 1 << ' ';
	// cerr << '\n';
	// for(int i = 1; i <= n; ++i){
	// 	cerr << go[i - 1] << ' ';
	// }

	for(int &x: res) ++x;
	Answer(res);
}

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