oj.uz

Submission #331138

# Submission time Handle Problem Language Result Execution time Memory
331138 2020-11-27T13:50:08 Z pit4h Library (JOI18_library) C++14
100 / 100
 495 ms 760 KB 
#include<bits/stdc++.h>
#include "library.h"
using namespace std;
using vi = vector<int>;

int n;

vector<vi> sub(vector<vi>& vec, int l, int r) {
	vector<vi> res;
	for(int i=l; i<=r; ++i) {
		res.push_back(vec[i]);
	}
	return res;
}

int qry(int x, int y) {
	vector<int> M(n);
	M[x-1] = M[y-1] = 1;
	return Query(M);
}
int qry(vi& v1, vi& v2) {
	vector<int> M(n);
	for(int i: v1) M[i-1] = 1;
	for(int i: v2) M[i-1] = 1;
	return Query(M);
}
int qry(vi v, vector<vi> V) {
	vector<int> M(n);
	for(int i: v) M[i-1] = 1;
	for(vi i: V) for(int j: i) M[j-1] = 1;
	return Query(M);
}
void rec(vi& v, vector<vi>& V, int l, int r) {
	if(l==r) {
		if(qry(v[0], V[l][0])==1) {
			reverse(v.begin(), v.end());
		}
		else if(qry(v.back(), V[l].back())==1) {
			reverse(V[l].begin(), V[l].end());
		}
		else if(qry(v[0], V[l].back())==1) {
			reverse(v.begin(), v.end());
			reverse(V[l].begin(), V[l].end());
		}
		for(int i: V[l]) v.push_back(i);
		V[l].clear();
		return;
	}

	int mid = (l+r)/2;
	if(qry(v, sub(V, l, mid)) <= mid-l+1) {
		rec(v, V, l, mid);
	}
	if(qry(v, sub(V, mid+1, r)) <= r-(mid+1)+1) {
		rec(v, V, mid+1, r);
	}
}
vector<vi> solve(vector<vi>& vec, int l, int r) {
	if(l==r) {
		return vector<vi>{vec[l]};
	}
	int mid = (l+r)/2;
	vector<vi> v1, v2;
	v1 = solve(vec, l, mid);
	v2 = solve(vec, mid+1, r);

	for(vi v: v1) {
		if(qry(v, v2) <= (int)v2.size()) {
			rec(v, v2, 0, (int)v2.size()-1);	
			vector<vi> new_v2;
			for(auto i: v2) {
				if(!i.empty()) new_v2.push_back(i);
			}
			v2 = new_v2;
		}
		v2.push_back(v);
	}
	/*cerr<<"solve("<<l<<' '<<r<<"): ";
	for(auto i: v2) {
		cerr<<"{";
		for(int j: i) {
			cerr<<j<<' ';
		}
		cerr<<"} ";
	}
	cerr<<'\n';*/
	return v2;
}
void Solve(int N)
{
	n = N;
	vector<vi> vec(N);
	for(int i=0; i<n; ++i) {
		vec[i].push_back(i+1);
	}
	random_shuffle(vec.begin(), vec.end());
	auto res = solve(vec, 0, n-1);
	/*cerr<<res.size()<<'\n';
	for(int i: res[0]) {
		cerr<<i<<' ';
	}
	cerr<<'\n';*/
	Answer(res.back());
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 364 KB # of queries: 2500
2 Correct 29 ms 388 KB # of queries: 2532
3 Correct 49 ms 364 KB # of queries: 2683
4 Correct 37 ms 364 KB # of queries: 2615
5 Correct 51 ms 364 KB # of queries: 2595
6 Correct 31 ms 388 KB # of queries: 2621
7 Correct 43 ms 364 KB # of queries: 2735
8 Correct 50 ms 492 KB # of queries: 2593
9 Correct 47 ms 364 KB # of queries: 2630
10 Correct 28 ms 492 KB # of queries: 1516
11 Correct 0 ms 364 KB # of queries: 0
12 Correct 1 ms 364 KB # of queries: 2
13 Correct 1 ms 364 KB # of queries: 4
14 Correct 1 ms 364 KB # of queries: 8
15 Correct 2 ms 364 KB # of queries: 68
16 Correct 4 ms 364 KB # of queries: 192

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 364 KB # of queries: 2500
2 Correct 29 ms 388 KB # of queries: 2532
3 Correct 49 ms 364 KB # of queries: 2683
4 Correct 37 ms 364 KB # of queries: 2615
5 Correct 51 ms 364 KB # of queries: 2595
6 Correct 31 ms 388 KB # of queries: 2621
7 Correct 43 ms 364 KB # of queries: 2735
8 Correct 50 ms 492 KB # of queries: 2593
9 Correct 47 ms 364 KB # of queries: 2630
10 Correct 28 ms 492 KB # of queries: 1516
11 Correct 0 ms 364 KB # of queries: 0
12 Correct 1 ms 364 KB # of queries: 2
13 Correct 1 ms 364 KB # of queries: 4
14 Correct 1 ms 364 KB # of queries: 8
15 Correct 2 ms 364 KB # of queries: 68
16 Correct 4 ms 364 KB # of queries: 192
17 Correct 495 ms 620 KB # of queries: 18600
18 Correct 445 ms 628 KB # of queries: 18356
19 Correct 473 ms 652 KB # of queries: 18498
20 Correct 439 ms 624 KB # of queries: 17352
21 Correct 379 ms 492 KB # of queries: 16303
22 Correct 417 ms 712 KB # of queries: 18492
23 Correct 432 ms 644 KB # of queries: 18633
24 Correct 136 ms 492 KB # of queries: 8294
25 Correct 369 ms 760 KB # of queries: 18172
26 Correct 397 ms 628 KB # of queries: 16921
27 Correct 150 ms 364 KB # of queries: 8224
28 Correct 449 ms 748 KB # of queries: 18683
29 Correct 418 ms 620 KB # of queries: 18664
30 Correct 451 ms 632 KB # of queries: 18683