Submission #130205

#	Time	Username	Problem	Language	Result	Execution time	Memory
130205		RockyB	Library (JOI18_library)	C++17	19 / 100	721 ms	2936 KiB

library

#include "library.h"

#include <bits/stdc++.h>

using namespace std;

const int MAXN = (int)1e5 + 7;

vector <int> g[MAXN];

void Solve(int N) {
	for (int i = 1; i <= N; i++) {
		{
			int l = i + 1, r = N, add = -1;
			while (l <= r) {
				int mid = l + r >> 1;
				vector <int> A(N);
				for (int j = mid; j <= N; j++) A[j - 1] = 1;
				int c1 = Query(A);
				A[i - 1] = 1;
				int c2 = Query(A);
				if (c1 < c2) r = mid - 1;
				else add = mid, l = mid + 1;
			}
			if (add != -1) {
				g[i].push_back(add);
				g[add].push_back(i);
			}
		}
		{
			int l = i + 1, r = N, add = -1;
			while (l <= r) {
				int mid = l + r >> 1;
				vector <int> A(N);
				for (int j = mid; j <= N; j++) A[j - 1] = 1;
				int c1 = Query(A);
				A[i - 1] = 1;
				int c2 = Query(A);
				if (c1 <= c2) r = mid - 1;
				else add = mid, l = mid + 1;
			}
			if (add != -1) {
				g[i].push_back(add);
				g[add].push_back(i);
			}
			// cerr << i << ' ' << add << endl;
		}
	}		


	int v = -1, p = -1;
	vector <int> ans;
	for (int i = 1; i <= N; i++) {
		// cerr << i << " -> " << g[i].size() << endl;
		if (g[i].size() <= 1) {
			v = i;
			break;
		}
	}
	while (ans.size() < N) {
		ans.push_back(v);
		for (auto it : g[v]) {
			if (it != p) {
				p = v;
				v = it;
				break;
			}
		}
	}
	// for (auto it : ans) cerr << it << ' ';
	Answer(ans);
}

Compilation message (stderr)

library.cpp: In function 'void Solve(int)':
library.cpp:16:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
library.cpp:33:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
library.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (ans.size() < N) {
         ~~~~~~~~~~~^~~

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