답안 #446053

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
446053 2021-07-20T15:01:16 Z flappybird 도서관 (JOI18_library) C++14
100 / 100
615 ms 704 KB
#include <bits/stdc++.h>
#include <cassert>
#include "library.h"
using namespace std;
typedef int ll;

vector<ll> asdf;
vector<ll> chk;
vector<ll> p, e, memo;
vector<ll> rs, s;
ll n;

void randp(ll N) {
	p.clear();
	p.resize(N);
	ll i;
	for (i = 0; i < N; i++) p[i] = i + 1;
	for (i = N - 1; i >= 1; i--) {
		if ((rand() % (i + 1))) {
			ll a;
			a = rand() % i;
			swap(p[i], p[a]);
		}
	}
}

ll cnt = 0;

ll query(vector<ll> v) {
	ll i;
	for (i = 0; i < v.size(); i++) v[i] = s[v[i]];
	cnt++;
	vector<ll> a;
	a.resize(n);
	for (auto x : v) a[x - 1] = 1;
	return Query(a);
}

void Solve(int N) {
	n = N;
	s.resize(1);
	rs.resize(N + 1);
	randp(N);
	for (auto x : p) s.push_back(x);
	srand(time(NULL));
	chk.resize(N + 1);
	ll i, a;
	for (i = 1; i <= N; i++) rs[s[i]] = i;
	ll sz = N;
	while (1) {
		asdf.clear();
		for (ll i = 1; i <= N; i++) if (!chk[i]) asdf.push_back(i);
		sz = asdf.size();
		if (!sz) break;
		if (asdf.size() <= 2) {
			e.push_back(asdf[0]);
			chk[asdf[0]] = 1;
			continue;
		}
		vector<ll> q1, q2;
		if (memo.empty()) {
			do {
				randp(sz);
				q1.clear();
				q2.clear();
				for (i = 0; i < sz; i++) {
					if (p[i] <= sz / 2) q1.push_back(asdf[i]);
					else q2.push_back(asdf[i]);
				}
			} while ((query(q1) + query(q2)) % 2);
			//memo = q2;
		}
		else {
			vector<ll> aasdf;
			aasdf.resize(N + 1);
			for (i = 1; i <= N; i++) aasdf[i] = chk[i];
			for (auto x : memo) aasdf[x] = 1;
			q1 = memo;
			for (i = 1; i <= N; i++) if (!aasdf[i]) q2.push_back(i);
			memo.clear();
		}
		ll l, r;
		l = 0, r = q1.size() - 1;
		vector<ll> v1, v2;
		while (l < r) {
			v1 = q1;
			v2 = q2;
			ll mid = (l + r) / 2;
			for (ll k = mid + 1; k < q1.size(); k++) v2.push_back(v1[k]);
			for (ll k = mid + 1; k < q1.size(); k++) v1.pop_back();
			if ((query(v1) + query(v2)) % 2) l = mid + 1;
			else r = mid;
		}
		e.push_back(q1[r]);
		chk[q1[r]] = 1;

		swap(q1, q2);
		l = 0, r = q1.size() - 1;
		v1.clear();
		v2.clear();
		while (l < r) {
			v1 = q1;
			v2 = q2;
			ll mid = (l + r) / 2;
			for (ll k = mid + 1; k < q1.size(); k++) v2.push_back(v1[k]);
			for (ll k = mid + 1; k < q1.size(); k++) v1.pop_back();
			if ((query(v1) + query(v2)) % 2) l = mid + 1;
			else r = mid;
		}
		e.push_back(q1[r]);
		chk[q1[r]] = 1;
	}
	deque<ll> d;
	for (i = N - 1; i >= 0; i--) {
		if (d.empty()) {
			d.push_back(e[i]);
			continue;
		}
		ll b = d.back();
		vector<ll> v;
		v.push_back(b);
		v.push_back(e[i]);
		if (query(v) == 1) d.push_back(e[i]);
		else d.push_front(e[i]);
	}
	vector<ll> ans;
	while (!d.empty()) {
		ans.push_back(d.back());
		d.pop_back();
	}
	for (i = 0; i < N; i++) ans[i] = s[ans[i]];
	Answer(ans);
}

Compilation message

library.cpp: In function 'll query(std::vector<int>)':
library.cpp:31:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for (i = 0; i < v.size(); i++) v[i] = s[v[i]];
      |              ~~^~~~~~~~~~
library.cpp: In function 'void Solve(int)':
library.cpp:89:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |    for (ll k = mid + 1; k < q1.size(); k++) v2.push_back(v1[k]);
      |                         ~~^~~~~~~~~~~
library.cpp:90:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |    for (ll k = mid + 1; k < q1.size(); k++) v1.pop_back();
      |                         ~~^~~~~~~~~~~
library.cpp:105:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |    for (ll k = mid + 1; k < q1.size(); k++) v2.push_back(v1[k]);
      |                         ~~^~~~~~~~~~~
library.cpp:106:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |    for (ll k = mid + 1; k < q1.size(); k++) v1.pop_back();
      |                         ~~^~~~~~~~~~~
library.cpp:47:8: warning: unused variable 'a' [-Wunused-variable]
   47 |  ll i, a;
      |        ^
# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 200 KB # of queries: 2589
2 Correct 49 ms 200 KB # of queries: 2522
3 Correct 49 ms 432 KB # of queries: 2671
4 Correct 52 ms 432 KB # of queries: 2713
5 Correct 42 ms 304 KB # of queries: 2751
6 Correct 58 ms 316 KB # of queries: 2735
7 Correct 54 ms 432 KB # of queries: 2673
8 Correct 53 ms 304 KB # of queries: 2624
9 Correct 56 ms 320 KB # of queries: 2716
10 Correct 25 ms 200 KB # of queries: 1620
11 Correct 0 ms 200 KB # of queries: 0
12 Correct 0 ms 200 KB # of queries: 1
13 Correct 1 ms 200 KB # of queries: 6
14 Correct 1 ms 200 KB # of queries: 9
15 Correct 2 ms 200 KB # of queries: 90
16 Correct 4 ms 200 KB # of queries: 206
# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 200 KB # of queries: 2589
2 Correct 49 ms 200 KB # of queries: 2522
3 Correct 49 ms 432 KB # of queries: 2671
4 Correct 52 ms 432 KB # of queries: 2713
5 Correct 42 ms 304 KB # of queries: 2751
6 Correct 58 ms 316 KB # of queries: 2735
7 Correct 54 ms 432 KB # of queries: 2673
8 Correct 53 ms 304 KB # of queries: 2624
9 Correct 56 ms 320 KB # of queries: 2716
10 Correct 25 ms 200 KB # of queries: 1620
11 Correct 0 ms 200 KB # of queries: 0
12 Correct 0 ms 200 KB # of queries: 1
13 Correct 1 ms 200 KB # of queries: 6
14 Correct 1 ms 200 KB # of queries: 9
15 Correct 2 ms 200 KB # of queries: 90
16 Correct 4 ms 200 KB # of queries: 206
17 Correct 606 ms 472 KB # of queries: 18119
18 Correct 609 ms 480 KB # of queries: 17970
19 Correct 564 ms 600 KB # of queries: 18161
20 Correct 549 ms 616 KB # of queries: 16945
21 Correct 488 ms 492 KB # of queries: 15956
22 Correct 577 ms 456 KB # of queries: 18299
23 Correct 615 ms 704 KB # of queries: 18188
24 Correct 214 ms 464 KB # of queries: 8328
25 Correct 537 ms 480 KB # of queries: 17738
26 Correct 529 ms 604 KB # of queries: 16474
27 Correct 228 ms 352 KB # of queries: 8248
28 Correct 575 ms 596 KB # of queries: 18221
29 Correct 609 ms 448 KB # of queries: 18148
30 Correct 615 ms 332 KB # of queries: 18197