oj.uz

Submission #940621

# Submission time Handle Problem Language Result Execution time Memory
940621 2024-03-07T11:53:14 Z WonderfulWhale Library (JOI18_library) C++17
19 / 100
 2000 ms 4160 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 90 ms 1216 KB # of queries: 1324
2 Correct 90 ms 1232 KB # of queries: 1313
3 Correct 108 ms 1484 KB # of queries: 1387
4 Correct 98 ms 1208 KB # of queries: 1366
5 Correct 101 ms 1284 KB # of queries: 1372
6 Correct 95 ms 1200 KB # of queries: 1373
7 Correct 104 ms 1260 KB # of queries: 1370
8 Correct 89 ms 1468 KB # of queries: 1305
9 Correct 109 ms 1504 KB # of queries: 1389
10 Correct 43 ms 708 KB # of queries: 822
11 Correct 0 ms 760 KB # of queries: 0
12 Correct 1 ms 432 KB # of queries: 2
13 Correct 0 ms 432 KB # of queries: 4
14 Correct 0 ms 440 KB # of queries: 8
15 Correct 1 ms 440 KB # of queries: 53
16 Correct 3 ms 436 KB # of queries: 119

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 1216 KB # of queries: 1324
2 Correct 90 ms 1232 KB # of queries: 1313
3 Correct 108 ms 1484 KB # of queries: 1387
4 Correct 98 ms 1208 KB # of queries: 1366
5 Correct 101 ms 1284 KB # of queries: 1372
6 Correct 95 ms 1200 KB # of queries: 1373
7 Correct 104 ms 1260 KB # of queries: 1370
8 Correct 89 ms 1468 KB # of queries: 1305
9 Correct 109 ms 1504 KB # of queries: 1389
10 Correct 43 ms 708 KB # of queries: 822
11 Correct 0 ms 760 KB # of queries: 0
12 Correct 1 ms 432 KB # of queries: 2
13 Correct 0 ms 432 KB # of queries: 4
14 Correct 0 ms 440 KB # of queries: 8
15 Correct 1 ms 440 KB # of queries: 53
16 Correct 3 ms 436 KB # of queries: 119
17 Execution timed out 2123 ms 4160 KB Time limit exceeded
18 Halted 0 ms 0 KB -