oj.uz

Submission #940622

# Submission time Handle Problem Language Result Execution time Memory
940622 2024-03-07T11:54:04 Z WonderfulWhale Library (JOI18_library) C++17
100 / 100
 107 ms 1468 KB 
#include<bits/stdc++.h>
#include"library.h"
using namespace std;

#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int N;

vector<vector<int>> V;

bool f(vector<int> v, int X, int exl=-1) {
	vector<int> q(N, 0);
	q[X] = 1;
	bool skip = false;
	for(int x:v) {
		if(x==exl) {
			skip = true;
			continue;
		}
		for(int y:V[x])
			q[y] = 1;
	}
	//cerr << "we want to achieve: " << sz(v)-skip << "\n";
	return Query(q)<=sz(v)-skip;
}

int Find(vector<int> v, int X, int exl=-1) {
	//cerr << "Find ";
	//for(int x:v) cerr << x << " ";
	//cerr << "\n";
	if(sz(v)==1)
		return v[0];
	vector<int> v1, v2;
	for(int i=0;i<sz(v);i++) {
		if(i%2==0) v1.pb(v[i]);
		else v2.pb(v[i]);
	}
	if(f(v1, X, exl)) {
		//cerr << "going v1\n";
		return Find(v1, X, exl);
	} else {
		//cerr << "going v2\n";
		return Find(v2, X, exl);
	}
}

void Solve(int n) {	
	N = n;
	V.pb({0});
	for(int i=1;i<n;i++) {
		vector<int> q(N, 0);
		for(auto x:V)
			for(auto y:x)
				q[y] = 1;
		q[i] = 1;
		int x = Query(q)-sz(V);
		if(x==1) {
			//cerr << "new\n";
			V.pb({i});
		} else if(x==0) {
			//cerr << "glue\n";
			vector<int> v(sz(V));
			iota(all(v), 0);
			int y = Find(v, i);
			vector<int> q1(N, 0);
			q1[i] = 1;
			q1[V[y][0]] = 1;
			if(Query(q1)==1) reverse(all(V[y]));
			V[y].pb(i);
		} else {
			//cerr << "merge\n";
			vector<int> v(sz(V));
			iota(all(v), 0);
			int a = Find(v, i);
			//cerr << "found: " << a << "\n";
			int b = Find(v, i, a);
			//cerr << "found: " << b << "\n";
			vector<int> q1(N, 0);
			q1[i] = 1;
			q1[V[a][0]] = 1;
			if(Query(q1)==1) reverse(all(V[a]));
			vector<int> q2(N, 0);
			q2[i] = 1;
			q2[V[b].back()] = 1;
			if(Query(q2)==1) reverse(all(V[b]));
			V.emplace_back();
			for(int x:V[a]) V.back().pb(x);
			V.back().pb(i);
			for(int x:V[b]) V.back().pb(x);
			swap(V[a], V.back());
			V.pop_back();
			swap(V[b], V.back());
			V.pop_back();
		}
		//cerr << "after---\n";
		//for(auto x:V) {
			//for(int y:x)
				//cerr << y+1 << " ";
			//cerr << "\n";
		//}
		//cerr << "---\n";
	}
	vector<int> res;
	for(int x:V[0])
		res.pb(x+1);
	Answer(res);
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 692 KB # of queries: 1324
2 Correct 12 ms 692 KB # of queries: 1313
3 Correct 11 ms 696 KB # of queries: 1387
4 Correct 14 ms 1168 KB # of queries: 1366
5 Correct 12 ms 692 KB # of queries: 1372
6 Correct 11 ms 704 KB # of queries: 1373
7 Correct 11 ms 692 KB # of queries: 1370
8 Correct 9 ms 444 KB # of queries: 1305
9 Correct 10 ms 688 KB # of queries: 1389
10 Correct 10 ms 600 KB # of queries: 822
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 2
13 Correct 0 ms 344 KB # of queries: 4
14 Correct 0 ms 344 KB # of queries: 8
15 Correct 1 ms 344 KB # of queries: 53
16 Correct 1 ms 432 KB # of queries: 119

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 692 KB # of queries: 1324
2 Correct 12 ms 692 KB # of queries: 1313
3 Correct 11 ms 696 KB # of queries: 1387
4 Correct 14 ms 1168 KB # of queries: 1366
5 Correct 12 ms 692 KB # of queries: 1372
6 Correct 11 ms 704 KB # of queries: 1373
7 Correct 11 ms 692 KB # of queries: 1370
8 Correct 9 ms 444 KB # of queries: 1305
9 Correct 10 ms 688 KB # of queries: 1389
10 Correct 10 ms 600 KB # of queries: 822
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 2
13 Correct 0 ms 344 KB # of queries: 4
14 Correct 0 ms 344 KB # of queries: 8
15 Correct 1 ms 344 KB # of queries: 53
16 Correct 1 ms 432 KB # of queries: 119
17 Correct 95 ms 1008 KB # of queries: 9140
18 Correct 95 ms 1468 KB # of queries: 9065
19 Correct 106 ms 1468 KB # of queries: 9104
20 Correct 87 ms 760 KB # of queries: 8545
21 Correct 87 ms 948 KB # of queries: 8055
22 Correct 97 ms 1220 KB # of queries: 9177
23 Correct 107 ms 1000 KB # of queries: 9134
24 Correct 37 ms 964 KB # of queries: 4215
25 Correct 95 ms 1240 KB # of queries: 8955
26 Correct 82 ms 948 KB # of queries: 8373
27 Correct 39 ms 1208 KB # of queries: 4195
28 Correct 21 ms 708 KB # of queries: 1998
29 Correct 18 ms 1204 KB # of queries: 1996
30 Correct 19 ms 1464 KB # of queries: 1998