Submission #544671

#	Time	Username	Problem	Language	Result	Execution time	Memory
544671		blue	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	2362 ms	852 KiB

dango3

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include "dango3.h"
using namespace std;

namespace {

int variable_example = 1;

using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define sz(x) int(x.size())

int N, M;

}  // namespace	

int boolquery(vi& inset)
{
	vi qr;
	for(int i = 1; i <= N*M; i++)
		if(inset[i])
			qr.push_back(i);

	// cerr << "do query : ";
	// for(int i = 1; i <= N*M; i++) cerr << inset[i] << ' ';
	// 	cerr << '\n';

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

	return Query(qr);
}

void compute(vi lst)
{
	// cerr << "lst size = " << sz(lst) << '\n';
	int lists = sz(lst)/N;

	if(lists == 1) 
	{
		// cerr << "answering : ";
		// for(int k : lst) cerr << k << ' ';
		// 	cerr << '\n';
		Answer(lst);
	}
	else
	{
		// int lft = lists/2;

		vi trial(1+N*M, 0);
		for(int q : lst) trial[q] = 1;

		vi lftvec, rgtvec;
		for(int k : lst)
		{
			trial[k] = 0;
			if(boolquery(trial) >= lists/2)
			{
				// cerr << "pushing left\n";
				lftvec.push_back(k);
			}
			else
			{
				// cerr << "pushing right\n";
				trial[k] = 1;
				rgtvec.push_back(k);
			}
		}

		// cerr << "lftvec = ";
		// for(int v : lftvec) cerr << v << ' ';
		// 	cerr << '\n';
		// cerr << "\n\n\n";


		// if(sz(lst) == 15)
		{

			compute(lftvec);
			compute(rgtvec);
		}
	}
}		

void Solve(int N_, int M_)
{
	N = N_;
	M = M_;

	vi lst;
	for(int i = 1; i <= N*M; i++) lst.push_back(i);

	compute(lst);
}

Compilation message (stderr)

dango3.cpp:13:5: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
   13 | int variable_example = 1;
      |     ^~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 78 / 78