Submission #130207

#	Time	Username	Problem	Language	Result	Execution time	Memory
130207		RockyB	Library (JOI18_library)	C++17	100 / 100	431 ms	4580 KiB

library

#include "library.h"

#include <bits/stdc++.h>

using namespace std;

const int MAXN = (int)1000 + 7;

vector <int> g[MAXN];

int N;

int dp[MAXN];
int ask(int mid) {
	if (~dp[mid]) return dp[mid];
	vector <int> A(N);
	for (int j = mid; j <= N; j++) A[j - 1] = 1;
	return dp[mid] = Query(A);
}
int dp1[MAXN][MAXN];
int ask1(int i, int mid) {
	if (~dp1[i][mid]) return dp1[i][mid];
	// cerr << " -> " << i << ' ' << mid << endl;
	vector <int> A(N);
	for (int j = mid; j <= N; j++) A[j - 1] = 1;
	A[i - 1] = 1;
	return dp1[i][mid] = Query(A);
}

void Solve(int n) {
	N = n;
	// Copy 
	memset(dp, -1, sizeof(dp));
	memset(dp1, -1, sizeof(dp1));
	for (int i = 1; i <= N; i++) {
		int R = -1, L = N + 1;
		{
			int l = i + 1, r = N, add = -1;
			while (l <= r) {
				int mid = l + r >> 1;
				int c1 = ask(mid);
				int c2 = ask1(i, mid);
				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);
				R = add - 1;
			}
		}
		{
			int l = i + 1, r = R, add = -1;
			while (l <= r) {
				int mid = l + r >> 1;
				int c1 = ask(mid);
				int c2 = ask1(i, mid);
				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:40:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
library.cpp:55:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
library.cpp:36:15: warning: unused variable 'L' [-Wunused-variable]
   int R = -1, L = N + 1;
               ^
library.cpp:79:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (ans.size() < N) {
         ~~~~~~~~~~~^~~

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