제출 #731179

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

chameleon

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

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

using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vpii = vector<pii>;

namespace
{
	const int mx = 500;

	int variable_example = 0;

	#define sz(x) int(x.size())



	vvi isedge(1 + 2*mx, vi(1 + 2*mx, 0));
	vi edge[1 + 2*mx];


	void add_edge(int u, int v)
	{
		isedge[u][v] = isedge[v][u] = 1;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}


	int addQuery(vi lst, int u)
	{
		lst.push_back(u);
		return Query(lst);
	}


	int findEdge(int u, vi lst) //lst is list of homogenous-bipartite-colored nodes
	{
		if(addQuery(lst, u) == sz(lst) + 1)
			return -1;

		while(sz(lst) > 1)
		{
			vi lstleft, lstright;
			for(int i = 0; i < sz(lst); i++)
			{
				if(i < sz(lst)/2)
					lstleft.push_back(lst[i]);
				else
					lstright.push_back(lst[i]);
			}

			if(addQuery(lstleft, u) != sz(lstleft) + 1)
				lst = lstleft;
			else
				lst = lstright;
		}

		return lst[0];
	}

};


void Solve(int N)
{
	for(int u = 1; u <= 2*N; u++)
	{
		vi col(1 + 2*N, -1);
		queue<int> tbv;

		vi collist[2];

		for(int i = 1; i < u; i++)
		{
			if(col[i] != -1)
				continue;

			col[i] = 0;

			tbv.push(i);

			while(!tbv.empty())
			{
				int x = tbv.front();
				tbv.pop();

				for(int y : edge[x])
				{
					if(col[y] != -1)
						continue;

					col[y] = col[x] ^ 1;

					tbv.push(y);
				}
			}
		}

		for(int i = 1; i < u; i++)
			collist[col[i]].push_back(i);

		for(int z = 0; z < 2; z++)
		{
			for(int t = 0; t < 3; t++)
			{
				int d = findEdge(u, collist[z]);
				if(d == -1)
					break;
				else
				{
					add_edge(u, d);
					// cerr << "adding edge " << u << ' ' << d << '\n';

					vi nl;
					for(int h : collist[z])
						if(h != d)
							nl.push_back(h);

					collist[z] = nl;
				}
			}
		}
	}




	vpii anslist;

	vi love(1 + 2*N, 0);

	for(int u = 1; u <= 2*N; u++)
	{
		if(sz(edge[u]) == 1)
		{
			;
		}
		else
		{
			assert(sz(edge[u]) == 3);

			if(Query({u, edge[u][0], edge[u][1]}) == 1)
				love[u] = edge[u][2];
			else if(Query({u, edge[u][0], edge[u][2]}) == 1)
				love[u] = edge[u][1];
			else
				love[u] = edge[u][0];
		}
	}

	for(int u = 1; u <= 2*N; u++)
	{
		for(int v = u+1; v <= 2*N; v++)
		{
			if(!isedge[u][v])
				continue;

			if(love[u] == v)
				continue;

			if(love[v] == u)
				continue;

			Answer(u, v);
		}
	}

	// cerr << "anslist size = " << sz(anslist) << '\n';

	// for(pii al : anslist)
	// {
	// 	if(al.first < al.second)
	// 	{
	// 		cerr << "answer : " << al.first << ' ' << al.second << '\n';
	// 		// Answer(al.first, al.second);
	// 	}
	// }
}

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

chameleon.cpp:17:6: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
   17 |  int variable_example = 0;
      |      ^~~~~~~~~~~~~~~~

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