Submission #1054052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054052		socpite	Chameleon's Love (JOI20_chameleon)	C++17	100 / 100	38 ms	720 KiB

chameleon

#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e3+5;

namespace {
	vector<int> g[maxn];
}  // namespace

int bs_edge(vector<int> vec, int x){
	int l = 0, r = vec.size()-2;
	while(l < r){
		int mid = (l+r+1)>>1;
		vector<int> nw(vec.begin(), vec.begin()+mid);
		nw.push_back(x);
		if(Query(nw) != nw.size())r = mid-1;
		else l = mid;
	}
	return vec[l];
}

void get_edge(vector<int> vec, int d = 2){
	vector<int> bp, oth;
	for(auto v: vec){
		bp.push_back(v);
		if(Query(bp) != bp.size()){
			bp.pop_back();
			oth.push_back(v);
		}
	}
	vector<int> rmv;
	for(auto v: oth){
		vector<int> nw = bp;
		nw.push_back(v);
		bool first = 1;
		while(g[v].size() < 3 && (first || Query(nw) != nw.size())){
			first = 0;
			int tmp = bs_edge(nw, v);
			nw.erase(find(nw.begin(), nw.end(), tmp));
			g[tmp].push_back(v);
			g[v].push_back(tmp);
		}
		if(g[v].size() == 3)rmv.push_back(v);
	}
	for(auto v: rmv)oth.erase(find(oth.begin(), oth.end(), v));
	if(d)get_edge(oth, d-1);
}

void Solve(int N) {
	set<pair<int, int>> bad;
	
	vector<int> vec(N*2);
	iota(vec.begin(), vec.end(), 1);
	get_edge(vec);

	for(int i = 1; i <= 2*N; i++){
		if(g[i].size() == 3){
			g[i].push_back(i);
			for(int j = 0; j < 3; j++){
				vector<int> nw = g[i];
				nw.erase(nw.begin() + j);
				if(Query(nw) == 1){
					bad.insert({i, g[i][j]});
					bad.insert({g[i][j], i});
				}
			}
			g[i].pop_back();
		}
	}
	for(int i = 1; i <= 2*N; i++){
		for(int v: g[i]){
			if(v > i)continue;
			if(bad.find({v, i}) == bad.end()){
				Answer(v, i);
			}
		}
	}
}

Compilation message (stderr)

chameleon.cpp: In function 'int bs_edge(std::vector<int>, int)':
chameleon.cpp:17:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |   if(Query(nw) != nw.size())r = mid-1;
      |      ~~~~~~~~~~^~~~~~~~~~~~
chameleon.cpp: In function 'void get_edge(std::vector<int>, int)':
chameleon.cpp:27:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   if(Query(bp) != bp.size()){
      |      ~~~~~~~~~~^~~~~~~~~~~~
chameleon.cpp:37:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   while(g[v].size() < 3 && (first || Query(nw) != nw.size())){
      |                                      ~~~~~~~~~~^~~~~~~~~~~~

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