제출 #245375

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
245375		kostia244	카멜레온의 사랑 (JOI20_chameleon)	C++17	24 / 100	43 ms	564 KiB

chameleon

#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
vector<int> merge(vector<int> a, vector<int> b) {
	for(auto i : b) a.push_back(i);
	return a;
}
bool add(vector<int> x, vector<int> v) {
	for(auto i : v) x.push_back(i);
	return x.size()<=500 && Query(x) == x.size();
}
vector<int> seg(vector<int> v, int l, int r) {
	vector<int> res;
	while(l <= r) res.push_back(v[l++]);
	return res;
}
vector<int> pref(vector<int> v, int x) {
	return seg(v, 0, x);
}
void Solve(int n) {
	vector<vi> g(2*n+1);
	vi t[4];
	for(int i = 1; i <= 2*n; i++) {
		int x = 0;
		while(x < 3 && !add(t[x], {i})) x++;
		t[x].push_back(i);
	}
	
	for(int i = 4; i-- > 1;) {
		//cout << i << " " << t[i].size() << "WTFWTF\n";
		for(int v, _v = 0; _v < t[i].size(); _v++) {
			v = t[i][_v];
			//cout << v << "Here" << endl;
			int j = i-1, f = 0, it = 0;
			while(j >= 0 && g[v].size() < 3) {
				for(int z = 1<<9; z>>=1;)
					if(f+z-1 < t[j].size() && add(seg(t[j],  f, f+z-1), {v})) f += z;
				if(f == t[j].size()) {
					//cout << "Bye\n";
					--j;
					++it;
					f = 0;
					continue;
				}
				
				g[v].push_back(t[j][f]);
				g[t[j][f]].push_back(v);
			
				//cout << v << " --- " << j << " / " << f << " " << t[j][f] << '\n';
			
				++f;
				if(i == 3) j--, f = 0;
				if(i == 2 && j && (it == 1 || !add(seg(t[j], f, (int)t[j].size()-1), {v}))) j--, f = 0;
				
				++it;
			}
		}
		//cout <<"Still not dead\n";
	}
	
	set<pair<int, int>> bad;
	for(int i = 1; i <= 2*n; i++) {
		if(g[i].size() == 1) continue;
		if(Query({g[i][0], g[i][1], i}) == 1) bad.insert(minmax(g[i][2], i));
		else if(Query({g[i][0], g[i][2], i}) == 1) bad.insert(minmax(g[i][1], i));
		else bad.insert(minmax(g[i][0], i));
	}
	for(int i = 1; i <= 2*n; i++) {
		while(bad.count(minmax(i, g[i].back()))) g[i].pop_back();
		if(i < g[i].back())
		Answer(i, g[i].back());
	}
}

컴파일 시 표준 에러 (stderr) 메시지

chameleon.cpp: In function 'bool add(std::vector<int>, std::vector<int>)':
chameleon.cpp:11:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  return x.size()<=500 && Query(x) == x.size();
                          ~~~~~~~~~^~~~~~~~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:32:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int v, _v = 0; _v < t[i].size(); _v++) {
                      ~~~^~~~~~~~~~~~~
chameleon.cpp:38:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if(f+z-1 < t[j].size() && add(seg(t[j],  f, f+z-1), {v})) f += z;
         ~~~~~~^~~~~~~~~~~~~
chameleon.cpp:39:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(f == t[j].size()) {
        ~~^~~~~~~~~~~~~~

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