oj.uz

Submission #366152

# Submission time Handle Problem Language Result Execution time Memory
366152 2021-02-13T11:18:43 Z Rainbowbunny Library (JOI18_library) C++17
100 / 100
 394 ms 704 KB 
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <chrono>
#include <random>
#include <bitset>
#include <utility>
#include "library.h"
using namespace std;

int dsu[1005];
vector <int> Ask;
vector <int> Component[1005];

int Root(int node)
{
	return dsu[node] == node ? node : dsu[node] = Root(dsu[node]);
}

bool Adj(int N, int x, int y)
{
	for(int i = 0; i < N; i++)
	{
		Ask[i] = 0;
	}
	Ask[x] = 1;
	Ask[y] = 1;
	return Query(Ask) == 1;
}

void Solve(int N)
{
	Ask.resize(N);
	for(int i = 0; i < N; i++)
	{
		dsu[i] = i;
		Component[i].push_back(i);
	}
	for(int edges = 1; edges < N; edges++)
	{
		vector <int> Remain;
		for(int j = 0; j < N; j++)
		{
			if(Root(j) == j)
			{
				Remain.push_back(j);
			}
		}
		int l = 0, r = Remain.size() - 1;
		while(l < r)
		{
			int mid = (l + r) >> 1;
			for(int i = 0; i < N; i++)
			{
				Ask[i] = 0;
			}
			for(int i = 0; i <= mid; i++)
			{
				for(auto x : Component[Remain[i]])
				{
					Ask[x] = 1;
				}
			}
			if(Query(Ask) == mid + 1)
			{
				l = mid + 1;
			}
			else
			{
				r = mid;
			}
		}
		int u = l;
		if(edges == 6)
		{
			for(int i = 0; i < N; i++)
			{
				Ask[i] = 0;
			}
			for(int i = 0; i <= 1; i++)
			{
				for(auto x : Component[Remain[i]])
				{
					Ask[x] = 1;
				}
			}
		}
		l = 0, r = u - 1;
		while(l < r)
		{
			int mid = (l + r + 1) >> 1;
			for(int i = 0; i < N; i++)
			{
				Ask[i] = 0;
			}
			for(int i = mid; i <= u; i++)
			{
				for(auto x : Component[Remain[i]])
				{
					Ask[x] = 1;
				}
			}
			if(Query(Ask) == u - mid + 1)
			{
				r = mid - 1;
			}
			else
			{
				l = mid;
			}
		}
		int v = l;
		u = Remain[u], v = Remain[v];
		if(Adj(N, Component[u][0], Component[v][0]))
		{
			reverse(Component[v].begin(), Component[v].end());
			Component[v].insert(Component[v].end(), Component[u].begin(), Component[u].end());
		}
		else if(Adj(N, Component[u][0], Component[v].back()))
		{
			Component[v].insert(Component[v].end(), Component[u].begin(), Component[u].end());
		}
		else if(Adj(N, Component[u].back(), Component[v][0]))
		{
			Component[v].insert(Component[v].begin(), Component[u].begin(), Component[u].end());
		}
		else
		{
			reverse(Component[v].begin(), Component[v].end());
			Component[v].insert(Component[v].begin(), Component[u].begin(), Component[u].end());
		}
		Component[u].clear();
		dsu[u] = v;
	}
	for(int i = 0; i < N; i++)
	{
		if(Root(i) == i)
		{
			for(auto &x : Component[i])
			{
				x++;
			}
			Answer(Component[i]);
		}
	}
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 364 KB # of queries: 2448
2 Correct 35 ms 384 KB # of queries: 2437
3 Correct 37 ms 364 KB # of queries: 2564
4 Correct 38 ms 540 KB # of queries: 2571
5 Correct 41 ms 364 KB # of queries: 2561
6 Correct 37 ms 364 KB # of queries: 2530
7 Correct 41 ms 364 KB # of queries: 2546
8 Correct 35 ms 492 KB # of queries: 2439
9 Correct 41 ms 364 KB # of queries: 2556
10 Correct 28 ms 384 KB # of queries: 1494
11 Correct 0 ms 364 KB # of queries: 0
12 Correct 0 ms 364 KB # of queries: 2
13 Correct 1 ms 364 KB # of queries: 5
14 Correct 1 ms 364 KB # of queries: 11
15 Correct 2 ms 364 KB # of queries: 91
16 Correct 4 ms 364 KB # of queries: 200

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 364 KB # of queries: 2448
2 Correct 35 ms 384 KB # of queries: 2437
3 Correct 37 ms 364 KB # of queries: 2564
4 Correct 38 ms 540 KB # of queries: 2571
5 Correct 41 ms 364 KB # of queries: 2561
6 Correct 37 ms 364 KB # of queries: 2530
7 Correct 41 ms 364 KB # of queries: 2546
8 Correct 35 ms 492 KB # of queries: 2439
9 Correct 41 ms 364 KB # of queries: 2556
10 Correct 28 ms 384 KB # of queries: 1494
11 Correct 0 ms 364 KB # of queries: 0
12 Correct 0 ms 364 KB # of queries: 2
13 Correct 1 ms 364 KB # of queries: 5
14 Correct 1 ms 364 KB # of queries: 11
15 Correct 2 ms 364 KB # of queries: 91
16 Correct 4 ms 364 KB # of queries: 200
17 Correct 369 ms 364 KB # of queries: 17344
18 Correct 354 ms 620 KB # of queries: 17074
19 Correct 393 ms 492 KB # of queries: 17341
20 Correct 374 ms 464 KB # of queries: 16209
21 Correct 302 ms 576 KB # of queries: 15252
22 Correct 350 ms 492 KB # of queries: 17429
23 Correct 359 ms 704 KB # of queries: 17350
24 Correct 146 ms 492 KB # of queries: 7929
25 Correct 394 ms 492 KB # of queries: 16982
26 Correct 349 ms 492 KB # of queries: 15867
27 Correct 145 ms 364 KB # of queries: 7886
28 Correct 217 ms 448 KB # of queries: 10974
29 Correct 229 ms 364 KB # of queries: 10962
30 Correct 250 ms 364 KB # of queries: 10974