Submission #1170658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170658		Bzslayed	Library (JOI18_library)	C++20	100 / 100	76 ms	460 KiB

library

#include <bits/stdc++.h>
#include "library.h"
using namespace std;
#define pii pair<int, int>

vector<pii> eds;
vector<int> adj[1005];
int calc(vector<int> &v){
	int cnt = 0;
	for (auto it : v){
		if (it) cnt++;
	}
	
	for (auto [x, y] : eds){
		if (v[x] && v[y]) cnt--;
	}
	
	return cnt;
}

vector<int> ans;
void dfs(int cur, int par){
	ans.push_back(cur+1);
	for (auto it : adj[cur]){
		if (it == par) continue;
		dfs(it, cur);
	}
}

void Solve(int n){
	vector<int> tst(n, 0);
	for (int i=2; i<=n; i++){
		for (int j=0; j<i; j++) tst[j] = 1;
		int x = Query(tst), y = calc(tst);
		if (x == y) continue;

		if (x == y-1){
			int lo = 0, hi = i-2; //book number i is book number i-1, so upper bounds starts at i-2
			while (lo < hi){
				int mid = (lo+hi)/2;
				for (int j=0; j<=mid; j++) tst[j] = 1;
				for (int j=mid+1; j<i-1; j++) tst[j] = 0;
				tst[i-1] = 1;
				
				int nx = Query(tst), ny = calc(tst);
				if (nx == ny-1) hi = mid;
				else lo = mid+1;
			}
			eds.push_back({lo, i-1}); //lo is the book that is connected to book number i
		}
		else{
			int lo = 0, hi = i-2;
			while (lo < hi){
				int mid = (lo+hi)/2;
				for (int j=0; j<=mid; j++) tst[j] = 1;
				for (int j=mid+1; j<i-1; j++) tst[j] = 0;
				tst[i-1] = 1;
				
				int nx = Query(tst), ny = calc(tst);
				if (nx == ny-2) hi = mid;
				else lo = mid+1;
			}
			eds.push_back({lo, i-1});

			lo = 0, hi = i-2;
			while (lo < hi){
				int mid = (lo+hi)/2;
				for (int j=0; j<=mid; j++) tst[j] = 1;
				for (int j=mid+1; j<i-1; j++) tst[j] = 0;
				tst[i-1] = 1;
				
				int nx = Query(tst), ny = calc(tst);
				if (nx == ny-1) hi = mid;
				else lo = mid+1;
			}
			eds.push_back({lo, i-1});
		}
	}

	for (auto [u, v] : eds){
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	for (int i=0; i<n; i++){
		if (adj[i].size() <= 1){
			dfs(i, -1);
			break;
		}
	}

	//cout << "size: " << ans.size() << "\n";

	Answer(ans);
}

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