Submission #221563

#	Time	Username	Problem	Language	Result	Execution time	Memory
221563		dorijanlendvaj	Library (JOI18_library)	C++14	0 / 100	482 ms	3204 KiB

library

#include "library.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#pragma GCC optimize("unroll-loops")
#define vi vector<int>
#define vl vector<ll>
#define all(a) begin(a),end(a)

using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;

int n,col[1010],par[1010];
vi sa[1010];
vi ch[1010];
map<pii,int> ma;
vi sol;

void merge(int a,int b)
{
	ch[a].pb(b);
	ch[b].pb(a);
	bool cha=col[a]==col[b];
	a=par[a];
	b=par[b];
	for (auto x: sa[b])
	{
		sa[a].pb(x);
		par[x]=a;
		if (cha) col[x]^=1;
	}
}

void dfs(int i,int p=-1)
{
	sol.pb(i+1);
	for (auto a: ch[i]) if (a!=p) dfs(a,i);
}

int f(int l,int r)
{
	if (r<=l) return r-l+1;
	if (ma.find({l,r})!=ma.end()) return ma[{l,r}];
	vi v;
	for (int j=0;j<l;++j) v.pb(0);
	for (int j=l;j<=r;++j) v.pb(1);
	for (int j=r+1;j<n;++j) v.pb(0);
	return ma[{l,r}]=Query(v);
}

void Solve(int N)
{
	n=N;
	for (int i=0;i<n;++i) par[i]=i,col[i]=0,sa[i]={i};
	int la=0;
	while (la<n-1)
	{
		int c=f(0,la)-la;
		while (f(0,la)-la==c) ++la;
		int dif=c-(f(0,la)-la);
		int lo=-1,hi=la-1;
		while (lo<hi)
		{
			int mid=(lo+hi+1)/2;
			vi v(n);
			int cn=0;
			for (int i=mid;i<la;++i) if (col[i]==0) v[i]=1,++cn;
			v[la]=1,++cn;
			if (Query(v)==cn)
			{
				cn=0;
				v=vi(n,0);
				for (int i=mid;i<la;++i) if (col[i]==1) v[i]=1,++cn;
				v[la]=1,++cn;
				if (Query(v)==cn) hi=mid-1;
				else lo=mid;
			}
			else lo=mid;
		}
		merge(la,lo);
		if (dif==2)
		{
			int pre=lo;
			lo=-1,hi=la-1;
			while (lo<hi)
			{
				int mid=(lo+hi+1)/2;
				vi v(n);
				int cn=0;
				for (int i=mid;i<la;++i) if (col[i]==0 && i!=pre) v[i]=1,++cn;
				v[la]=1,++cn;
				if (Query(v)==cn)
				{
					cn=0;
					v=vi(n,0);
					for (int i=mid;i<la;++i) if (col[i]==1 && i!=pre) v[i]=1,++cn;
					v[la]=1,++cn;
					if (Query(v)==cn) hi=mid-1;
					else lo=mid;
				}
				else lo=mid;
			}
			merge(la,lo);
		}
	}
	for (int i=0;i<n;++i) if (ch[i].size()==1)
	{
		dfs(i);
		break;
	}
	Answer(sol);
}

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