Submission #504034

#	Time	Username	Problem	Language	Result	Execution time	Memory
504034		AriaH	Library (JOI18_library)	C++17	0 / 100	56 ms	48008 KiB

library

/** I can do this all day **/

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "library.h"

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define SZ(x) (int)x.size()
#define Mp make_pair
#define endl "\n"
#define fast_io ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file_io freopen("inupt.txt", "r+", stdin); freopen("output.txt", "w+", stdout);

const int N = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
const int LOG = 20;

ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; }

int n;

vector < int > Q, G[N];

vector < pii > E;

/*
int Query(vector < int > vec)
{
	printf("query : \n");
	for(int i = 0; i < n; i ++)
	{
		printf("%d ", vec[i]);
	}
	int x;
	scanf("%d", &x);
	return x;
}

void Answer(vector < int > vec)
{
	printf("ans : \n");
	for(auto x : vec) printf("%d ", x);
	printf("\n");
}*/

void add(int a, int b)
{
	a ++, b ++;
	///printf("finde %d %d\n", a, b);
	G[a].push_back(b);
	G[b].push_back(a);
	E.push_back({a - 1, b - 1});
}

void Fill(int l, int r)
{
	for(int i = 0; i < l; i ++) Q[i] = 0;
	for(int i = r + 1; i < n; i ++) Q[i] = 0;
	for(int i = l; i <= r; i ++) Q[i] = 1;
}

int yal()
{
	int T = 0;
	for(int i = 0; i < n; i ++)
	{
		T += Q[i];
	}
	if(T <= 1) return 0;
	int cu = T - Query(Q);
	for(auto [a, b] : E)
	{
		if(Q[a] && Q[b]) cu --;
	}
	return cu;
}

inline int ask(int i, int l, int r)
{
	if(l > r || i >= l) return 0;
	Fill(l, r);
	int cu = yal();
	Q[i] = 1;
	int cu2 = yal();
	return cu2 - cu; 
}

void Solve(int _n)
{
	if(n == 1)
	{
		Answer({1});
	}
	n = _n;
	Q.resize(n, 0);
	E.clear();
	for(int i = 0; i < n; i ++) G[i].clear();
	for(int i = 0; i < n - 1; i ++)
	{
		int e = ask(i, i + 1, n - 1);
		///printf("i = %d e = %d\n", i, e);
		while(e --)
		{
			int d = i, up = n - 1;
			while(up - d > 1)
			{
				int mid = (up + d) >> 1;
				if(ask(i, i + 1, mid))
				{
					up = mid;
				}
				else
				{
					d = mid;
				}
			}
			add(i, up);
		}
	}
	int st = -1, last = 0;
	for(int i = 1; i <= n; i ++) if(SZ(G[i]) == 1) st = i;
	vector < int > Ans;
	assert(st != -1);
	while(1)
	{
		int nxt = 0;
		Ans.push_back(st);
		for(auto now : G[st]) nxt ^= now;
		nxt ^= last;
		last = st;
		st = nxt;
		if(st == 0) break;
	}
	Answer(Ans);
}
/*
int main()
{
	scanf("%d", &n);
	Solve(n);

	return 0;
}
*/

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