Submission #1020292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020292		ttamx	Chameleon's Love (JOI20_chameleon)	C++17	100 / 100	45 ms	600 KiB

chameleon

#include "chameleon.h"
#include <bits/stdc++.h>

using namespace std;

void Solve(int n){
	auto check=[&](vector<int> &a,int l,int r,int u){
		vector<int> b{u};
		for(int i=l;i<=r;i++)b.emplace_back(a[i]);
		return Query(b)<b.size();
	};
	auto bsearch=[&](vector<int> &a,int st,int u){
		int l=st,r=a.size();
		while(l<r){
			int m=(l+r)/2;
			if(check(a,st,m,u))r=m;
			else l=m+1;
		}
		return l;
	};
	vector<vector<int>> adj(2*n+1);
	for(int i=2;i<=2*n;i++){
		vector<int> col(i);
		function<void(int,int)> dfs=[&](int u,int c){
			if(col[u])return;
			col[u]=c;
			for(auto v:adj[u])dfs(v,3-c);
		};
		for(int j=1;j<i;j++)dfs(j,1);
		vector<int> comp[2];
		for(int j=1;j<i;j++)comp[col[j]-1].emplace_back(j);
		for(int j=0;j<2;j++){
			int st=0;
			while(check(comp[j],st,comp[j].size()-1,i)){
				st=bsearch(comp[j],st,i);
				int u=comp[j][st];
				adj[i].emplace_back(u);
				adj[u].emplace_back(i);
				st++;
			}
		}
	}
	vector<int> ans(2*n+1),val(2*n+1);
	for(int i=1;i<=2*n;i++){
		if(adj[i].size()==1){
			ans[i]=adj[i][0];
			ans[adj[i][0]]=i;
		}else{
			for(auto x:adj[i])val[i]^=x;
			while(Query({i,adj[i][0],adj[i][1]})>1){
				rotate(adj[i].begin(),adj[i].begin()+1,adj[i].end());
			}
			val[i]^=adj[i][2];
			val[adj[i][2]]^=i;
		}
	}
	for(int i=1;i<=2*n;i++){
		if(!ans[i])ans[i]=val[i];
		if(i<ans[i])Answer(i,ans[i]);
	}
}

Compilation message (stderr)

chameleon.cpp: In lambda function:
chameleon.cpp:10:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |   return Query(b)<b.size();
      |          ~~~~~~~~^~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36