답안 #130207

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
130207 2019-07-14T09:01:27 Z RockyB 도서관 (JOI18_library) C++17
100 / 100
431 ms 4580 KB
#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

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) {
         ~~~~~~~~~~~^~~
# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 4344 KB # of queries: 1990
2 Correct 40 ms 4312 KB # of queries: 2015
3 Correct 42 ms 4216 KB # of queries: 2131
4 Correct 32 ms 4392 KB # of queries: 2162
5 Correct 42 ms 4400 KB # of queries: 2136
6 Correct 40 ms 4316 KB # of queries: 2116
7 Correct 33 ms 4344 KB # of queries: 2133
8 Correct 37 ms 4344 KB # of queries: 2057
9 Correct 44 ms 4316 KB # of queries: 2123
10 Correct 19 ms 4316 KB # of queries: 1231
11 Correct 5 ms 4216 KB # of queries: 0
12 Correct 5 ms 4216 KB # of queries: 2
13 Correct 5 ms 4216 KB # of queries: 5
14 Correct 5 ms 4264 KB # of queries: 9
15 Correct 6 ms 4344 KB # of queries: 75
16 Correct 7 ms 4216 KB # of queries: 163
# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 4344 KB # of queries: 1990
2 Correct 40 ms 4312 KB # of queries: 2015
3 Correct 42 ms 4216 KB # of queries: 2131
4 Correct 32 ms 4392 KB # of queries: 2162
5 Correct 42 ms 4400 KB # of queries: 2136
6 Correct 40 ms 4316 KB # of queries: 2116
7 Correct 33 ms 4344 KB # of queries: 2133
8 Correct 37 ms 4344 KB # of queries: 2057
9 Correct 44 ms 4316 KB # of queries: 2123
10 Correct 19 ms 4316 KB # of queries: 1231
11 Correct 5 ms 4216 KB # of queries: 0
12 Correct 5 ms 4216 KB # of queries: 2
13 Correct 5 ms 4216 KB # of queries: 5
14 Correct 5 ms 4264 KB # of queries: 9
15 Correct 6 ms 4344 KB # of queries: 75
16 Correct 7 ms 4216 KB # of queries: 163
17 Correct 424 ms 4448 KB # of queries: 14554
18 Correct 404 ms 4344 KB # of queries: 14400
19 Correct 431 ms 4396 KB # of queries: 14431
20 Correct 374 ms 4580 KB # of queries: 13523
21 Correct 332 ms 4452 KB # of queries: 12766
22 Correct 360 ms 4444 KB # of queries: 14474
23 Correct 413 ms 4472 KB # of queries: 14534
24 Correct 150 ms 4344 KB # of queries: 6612
25 Correct 414 ms 4472 KB # of queries: 14216
26 Correct 362 ms 4324 KB # of queries: 13216
27 Correct 136 ms 4352 KB # of queries: 6600
28 Correct 265 ms 4344 KB # of queries: 9474
29 Correct 276 ms 4452 KB # of queries: 9463
30 Correct 262 ms 4572 KB # of queries: 9474