oj.uz

Submission #446019

# Submission time Handle Problem Language Result Execution time Memory
446019 2021-07-20T13:41:00 Z flappybird Library (JOI18_library) C++14
19 / 100
 673 ms 716 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;
ll n;

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

ll cnt = 0;

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

void Solve(int N) {
	n = N;
	srand(time(NULL));
	chk.resize(N + 1);
	ll i, a;
	ll sz = N;
	for (a = 1; a <= N; a++) {
		asdf.clear();
		for (ll i = 1; i <= N; i++) if (!chk[i]) asdf.push_back(i);
		sz = asdf.size();
		if (asdf.size() <= 2) {
			e.push_back(asdf[0]);
			chk[asdf[0]] = 1;
			continue;
		}
		vector<ll> q1, q2;
		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);
		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;
	}
	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();
	}
	Answer(ans);
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:67:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |    for (ll k = mid + 1; k < q1.size(); k++) v2.push_back(v1[k]);
      |                         ~~^~~~~~~~~~~
library.cpp:68:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |    for (ll k = mid + 1; k < q1.size(); k++) v1.pop_back();
      |                         ~~^~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 308 KB # of queries: 2947
2 Correct 60 ms 292 KB # of queries: 2918
3 Correct 61 ms 304 KB # of queries: 3087
4 Correct 62 ms 200 KB # of queries: 3083
5 Correct 54 ms 428 KB # of queries: 3063
6 Correct 64 ms 296 KB # of queries: 3059
7 Correct 64 ms 288 KB # of queries: 3125
8 Correct 52 ms 304 KB # of queries: 2980
9 Correct 45 ms 424 KB # of queries: 3050
10 Correct 35 ms 292 KB # of queries: 1830
11 Correct 0 ms 200 KB # of queries: 0
12 Correct 0 ms 200 KB # of queries: 1
13 Correct 0 ms 200 KB # of queries: 6
14 Correct 1 ms 200 KB # of queries: 13
15 Correct 3 ms 296 KB # of queries: 126
16 Correct 5 ms 200 KB # of queries: 242

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 308 KB # of queries: 2947
2 Correct 60 ms 292 KB # of queries: 2918
3 Correct 61 ms 304 KB # of queries: 3087
4 Correct 62 ms 200 KB # of queries: 3083
5 Correct 54 ms 428 KB # of queries: 3063
6 Correct 64 ms 296 KB # of queries: 3059
7 Correct 64 ms 288 KB # of queries: 3125
8 Correct 52 ms 304 KB # of queries: 2980
9 Correct 45 ms 424 KB # of queries: 3050
10 Correct 35 ms 292 KB # of queries: 1830
11 Correct 0 ms 200 KB # of queries: 0
12 Correct 0 ms 200 KB # of queries: 1
13 Correct 0 ms 200 KB # of queries: 6
14 Correct 1 ms 200 KB # of queries: 13
15 Correct 3 ms 296 KB # of queries: 126
16 Correct 5 ms 200 KB # of queries: 242
17 Runtime error 673 ms 716 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -