Submission #909886

#	Time	Username	Problem	Language	Result	Execution time	Memory
909886		mickey080929	Library (JOI18_library)	C++17	100 / 100	253 ms	1232 KiB

library

#include <bits/stdc++.h>
#include "library.h"

using namespace std;

int n;
vector<int> adj[1010];

int ask(vector<int> qry) {
	int k = 0;
	for (int i=0; i<n; i++) {
		k += qry[i];
	}
	int al = 0;
	for (int i=0; i<n; i++) {
		for (auto &j : adj[i]) {
			if (qry[i] && qry[j]) {
				al ++;
			}
		}
	}
	al /= 2;
	return k - Query(qry) - al;
}

void Solve(int N) {
	n = N;
	for (int i=0; i<N-1; i++) {
		int lo = 1, hi = N-1;
		while (lo < hi) {
			int mid = lo + hi >> 1;
			vector<int> qry(N, 0);
			for (int j=0; j<=mid; j++) {
				qry[j] = 1;
			}
			if (ask(qry)) hi = mid;
			else lo = mid + 1;
		}
		int r = lo;
		lo = 0; hi = r-1;
		while (lo < hi) {
			int mid = lo + hi + 1 >> 1;
			vector<int> qry(N, 0);
			for (int j=mid; j<=r; j++) {
				qry[j] = 1;
			}
			if (ask(qry)) lo = mid;
			else hi = mid - 1;
		}
		int l = lo;
		adj[l].push_back(r);
		adj[r].push_back(l);
	}
	int x;
	for (int i=0; i<n; i++) {
		if (adj[i].size() == 1) {
			x = i;
			break;
		}
	}
	vector<int> ans;
	int p = -1;
	while (true) {
		ans.push_back(x+1);
		int nxt = -1;
		for (auto &y : adj[x]) {
			if (y != p) {
				nxt = y;
			}
		}
		if (nxt == -1) break;
		p = x;
		x = nxt;
	}
	Answer(ans);
}

Compilation message (stderr)

library.cpp: In function 'void Solve(int)':
library.cpp:31:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |    int mid = lo + hi >> 1;
      |              ~~~^~~~
library.cpp:42:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |    int mid = lo + hi + 1 >> 1;
      |              ~~~~~~~~^~~
library.cpp:64:18: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |   ans.push_back(x+1);
      |                 ~^~

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