제출 #1225538

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1225538		mychecksedad	도서관 (JOI18_library)	C++20	0 / 100	16 ms	420 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);
	vi go(n, -1);

	for(int i = 0; i < n; ++i){
		int l = 0, r = n - 1, fine = -1;
		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;
			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){
			continue;
		}
		go[i] = fine;
		has[go[i]].pb(i);
	}
	vector<vi> g(n);
	for(int i = 0; i < n; ++i){
		if(go[i] == -1) continue;
		g[go[i]].pb(i);
		g[i].pb(go[i]);
	}

	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: 0 / 19
• Subtask 2: 0 / 81