Submission #1191956

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191956		peteza	Library (JOI18_library)	C++20	100 / 100	126 ms	476 KiB

library

#include <cstdio>
#include <vector>
#include <iostream>
#include "library.h"
using namespace std;

int exval[1005];
vector<int> adj[1005];
vector<int> ans;
bool vis[1005];

void dfs(int x) {
	vis[x] = 1; ans.push_back(x);
	for(auto &e:adj[x]) if(!vis[e]) dfs(e);
}

void Solve(int N)
{
	/*
	vector<int> M(N);

	for(int i = 0; i < N; i++) {
		M[i] = 1;
	}

	int A = Query(M);
	

	vector<int> res(N);

	for(int i = 0; i < N; i++) {
		res[i] = i + 1;
	}

	Answer(res);
	*/
	for(int i=1;i<=N;i++) exval[i] = i;
	for(int i=1;i<N;i++) {
		int l = 2, r = N, mid;
		while(l <= r) {
			mid = (l+r) >> 1;
			vector<int> toask(N);
			for(int i=0;i<mid;i++) toask[i] = 1;
			if(Query(toask) == exval[mid]) l = mid+1;
			else r = mid-1;
		}
		//cout << l;
		//r becomes the bla bla ble bla bla blo bla bla bla bla
		for(int i=l;i<=N;i++) exval[i]--;
		int cl = 1, cr = l-1;
		while(cl <= cr) {
			mid = (cl+cr) >> 1;
			vector<int> toask(N);
			for(int i=0;i<mid;i++) {
				toask[i] = 1;
			}
			toask[l-1] = 1;
			if(Query(toask) + (adj[l].empty() ? 0 : (adj[l][0] <= mid ? 1 : 0)) == exval[mid]+1) cl = mid+1;
			else cr = mid-1;
		}
		//cout << " Connected to " << cl << '\n';
		adj[l].push_back(cl);
		adj[cl].push_back(l);
	}
	for(int i=1;i<=N;i++) {
		if(adj[i].size()<2) {
			dfs(i);
			break;
		}
	}
	Answer(ans);
}

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