oj.uz

Submission #483664

# Submission time Handle Problem Language Result Execution time Memory
483664 2021-10-31T13:56:15 Z ymm Library (JOI18_library) C++17
100 / 100
 329 ms 328 KB 
///
///   You fell for it, fool!
///   Thunder Cross Split Attack!
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
typedef long long ll;
using namespace std;

#include "library.h"

const int N = 1010;
int n;

vector<int> v;
int cnt[N];
int adj[N][2];
int mp[N];

int qry2(int x, vector<int>& v, int k)
{
	vector<int> kooft(n);
	Loop(i,0,k) kooft[v[i]] = 1;
	kooft[x] = 1;
	return Query(kooft);
}

int getsize(vector<int>& v, int k)
{
	int ans = k;
	Loop(i,0,k) Loop(j,i+1,k)
		if(adj[v[i]][0] == v[j] || adj[v[i]][1] == v[j])
			--ans;
	return ans;
}

void add(int x)
{
	cnt[x]++;
	v[x] = 1;
	vector<int> can;
	Loop(y,0,n) if(y != x && cnt[y] > 0 && cnt[y] < 3)
	{
		can.push_back(y);
	}
	for(int _ = 0; _ < 2 && can.size(); ++_)
	{
		int l = 0, r = can.size();
		if(qry2(x,can,r) > getsize(can,r)) break;
		while(r-l > 1)
		{
			int m = (l+r)/2;
			if(qry2(x,can,m) <= getsize(can,m)) r = m;
			else l = m;
		}
		int y = can[l];
		adj[y][cnt[y]++-1] = x;
		adj[x][cnt[x]++-1] = y;
		can.erase(can.begin()+l);
	}
}

void make(int v, int p, vector<int>& ans)
{
	ans.push_back(v+1);
	if(adj[v][0] == p)
		{if(cnt[v] == 3) make(adj[v][1], v, ans);}
	else
		make(adj[v][0], v, ans);
}

void Solve(int _n)
{
	n = _n;
	v.resize(n);
	if(n==1){v[0] = 1; Answer(v); return;}

	srand(time(0));
	vector<int> josuke(n);
	iota(josuke.begin(), josuke.end(), 0);
	random_shuffle(josuke.begin(),josuke.end());
	for(int x : josuke) add(x);

	vector<int> ans;
	Loop(i,0,n) if(cnt[i] == 2)
		{make(i,-1,ans); break;}
	Answer(ans);
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 200 KB # of queries: 1381
2 Correct 23 ms 200 KB # of queries: 1374
3 Correct 18 ms 200 KB # of queries: 1465
4 Correct 21 ms 200 KB # of queries: 1448
5 Correct 22 ms 200 KB # of queries: 1457
6 Correct 21 ms 200 KB # of queries: 1460
7 Correct 26 ms 200 KB # of queries: 1422
8 Correct 24 ms 200 KB # of queries: 1384
9 Correct 18 ms 200 KB # of queries: 1451
10 Correct 12 ms 200 KB # of queries: 842
11 Correct 0 ms 200 KB # of queries: 0
12 Correct 1 ms 300 KB # of queries: 1
13 Correct 0 ms 200 KB # of queries: 4
14 Correct 0 ms 200 KB # of queries: 7
15 Correct 1 ms 296 KB # of queries: 59
16 Correct 1 ms 304 KB # of queries: 122

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 200 KB # of queries: 1381
2 Correct 23 ms 200 KB # of queries: 1374
3 Correct 18 ms 200 KB # of queries: 1465
4 Correct 21 ms 200 KB # of queries: 1448
5 Correct 22 ms 200 KB # of queries: 1457
6 Correct 21 ms 200 KB # of queries: 1460
7 Correct 26 ms 200 KB # of queries: 1422
8 Correct 24 ms 200 KB # of queries: 1384
9 Correct 18 ms 200 KB # of queries: 1451
10 Correct 12 ms 200 KB # of queries: 842
11 Correct 0 ms 200 KB # of queries: 0
12 Correct 1 ms 300 KB # of queries: 1
13 Correct 0 ms 200 KB # of queries: 4
14 Correct 0 ms 200 KB # of queries: 7
15 Correct 1 ms 296 KB # of queries: 59
16 Correct 1 ms 304 KB # of queries: 122
17 Correct 295 ms 324 KB # of queries: 9521
18 Correct 304 ms 200 KB # of queries: 9436
19 Correct 285 ms 200 KB # of queries: 9567
20 Correct 242 ms 200 KB # of queries: 8922
21 Correct 238 ms 200 KB # of queries: 8398
22 Correct 314 ms 200 KB # of queries: 9566
23 Correct 308 ms 200 KB # of queries: 9538
24 Correct 89 ms 304 KB # of queries: 4432
25 Correct 285 ms 308 KB # of queries: 9321
26 Correct 257 ms 328 KB # of queries: 8713
27 Correct 84 ms 200 KB # of queries: 4415
28 Correct 315 ms 200 KB # of queries: 9552
29 Correct 329 ms 200 KB # of queries: 9543
30 Correct 282 ms 200 KB # of queries: 9578