Submission #1156938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156938		minh30082008	Library (JOI18_library)	C++20	100 / 100	138 ms	492 KiB

library

#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include "library.h"

#include<bits/stdc++.h>
#define INF 1e18
#define fi first
#define se second
#define FOR(i, k, n) for(ll i = k; i <= n; i++)
#define FOR1(i, k, n) for(ll i = k; i >= n; i--)
#define pb push_back
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define vi vector<int>
#define pii pair<int, int>
#define vii vector<pii>
#define ll long long
#define vll vector<ll>
#define pll pair<ll, ll>
#define re return 0
#define mii map<int, int>
#define input "chinaflu.inp"
#define output "chinaflu.out"
#define rf 	freopen(input, "r", stdin); freopen(output, "w", stdout)
using namespace std;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 9;
const int base = 998244353;
void add(int &a, int b) 
{
	a += b; 
	if(a >= mod) a -= mod; 
	if(a < 0) a += mod; 
}
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r)
{
	return uniform_int_distribution<int>(l, r) (rd);
}
vi ask;
vi adj[1005];
vii adj1;
bool vis[1005];
bool check(int l, int r)
{
	FOR(i, 0, ask.size() - 1)
		ask[i] = 0;
	FOR(i, l - 1, r - 1)
		ask[i] = 1;	
	int res = r - l + 1;
	int tmp = Query(ask);
	for(auto x : adj1)
	{
		if(x.fi >= l && x.fi <= r && x.se >= l && x.se <= r)
			res--;
	}
	return res != tmp;
}
void Solve(int n)
{
	FOR(i, 0, n)
		vis[i] = 0;
	ask.clear();
	FOR(i, 1, n)
		ask.pb(0);
	FOR(i, 0, n)
		adj[i].clear();
	adj1.clear();
	while(adj1.size() < n - 1)
	{
		int l = 1, r = n;
		int vt;
		while(l <= r)
		{
			int mid = (l + r) >> 1;
			if(check(1, mid))
			{
				vt = mid;
				r = mid - 1;
			}
			else
				l = mid + 1;
		}
		l = 1, r = vt - 1;
		int vt1;
		while(l <= r)
		{
			int mid = (l + r) >> 1;
			if(check(mid, vt))
			{
				vt1 = mid;
				l = mid + 1;
			}
			else
				r = mid - 1;
		}
		adj1.pb({vt, vt1});
		adj[vt].pb(vt1);
		adj[vt1].pb(vt);
	}
	vi answer(n);
	int pos = 1;
	FOR(i, 1, n)
		if(adj[i].size() == 1)
			pos = i;
	queue<int> Q;
	Q.push(pos);
	vis[pos] = 1;
	int cnt = 0;
	while(!Q.empty())
	{
		int u = Q.front();
		Q.pop();
		answer[cnt] = u;
		++cnt;
		for(auto v : adj[u])
		{
			if(vis[v])
				continue;
			Q.push(v);
			vis[v] = 1;
		}
	}
	Answer(answer);
}

• Subtask 1: 19 / 19
• Subtask 2: 81 / 81