oj.uz

답안 #130205

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
130205 2019-07-14T08:52:25 Z RockyB 도서관 (JOI18_library) C++17
19 / 100
 721 ms 2936 KB 
#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

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.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 2552 KB # of queries: 4582
2 Correct 84 ms 2708 KB # of queries: 4556
3 Correct 79 ms 2792 KB # of queries: 4818
4 Correct 95 ms 2728 KB # of queries: 4828
5 Correct 71 ms 2680 KB # of queries: 4842
6 Correct 81 ms 2748 KB # of queries: 4814
7 Correct 78 ms 2752 KB # of queries: 4814
8 Correct 86 ms 2676 KB # of queries: 4634
9 Correct 66 ms 2660 KB # of queries: 4818
10 Correct 44 ms 2552 KB # of queries: 2784
11 Correct 4 ms 2552 KB # of queries: 0
12 Correct 4 ms 2552 KB # of queries: 4
13 Correct 4 ms 2684 KB # of queries: 12
14 Correct 5 ms 2552 KB # of queries: 20
15 Correct 6 ms 2680 KB # of queries: 156
16 Correct 11 ms 2680 KB # of queries: 358

Subtask #2
0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 2552 KB # of queries: 4582
2 Correct 84 ms 2708 KB # of queries: 4556
3 Correct 79 ms 2792 KB # of queries: 4818
4 Correct 95 ms 2728 KB # of queries: 4828
5 Correct 71 ms 2680 KB # of queries: 4842
6 Correct 81 ms 2748 KB # of queries: 4814
7 Correct 78 ms 2752 KB # of queries: 4814
8 Correct 86 ms 2676 KB # of queries: 4634
9 Correct 66 ms 2660 KB # of queries: 4818
10 Correct 44 ms 2552 KB # of queries: 2784
11 Correct 4 ms 2552 KB # of queries: 0
12 Correct 4 ms 2552 KB # of queries: 4
13 Correct 4 ms 2684 KB # of queries: 12
14 Correct 5 ms 2552 KB # of queries: 20
15 Correct 6 ms 2680 KB # of queries: 156
16 Correct 11 ms 2680 KB # of queries: 358
17 Incorrect 642 ms 2856 KB Wrong Answer [3]
18 Incorrect 659 ms 2800 KB Wrong Answer [3]
19 Incorrect 718 ms 2732 KB Wrong Answer [3]
20 Incorrect 634 ms 2936 KB Wrong Answer [3]
21 Incorrect 631 ms 2824 KB Wrong Answer [3]
22 Incorrect 715 ms 2800 KB Wrong Answer [3]
23 Incorrect 692 ms 2672 KB Wrong Answer [3]
24 Correct 266 ms 2804 KB # of queries: 15102
25 Incorrect 680 ms 2792 KB Wrong Answer [3]
26 Incorrect 649 ms 2816 KB Wrong Answer [3]
27 Correct 299 ms 2808 KB # of queries: 15020
28 Incorrect 721 ms 2804 KB Wrong Answer [3]
29 Incorrect 657 ms 2924 KB Wrong Answer [3]
30 Incorrect 705 ms 2936 KB Wrong Answer [3]