Submission #815558

#	Time	Username	Problem	Language	Result	Execution time	Memory
815558		Sohsoh84	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	181 ms	564 KiB

dango3

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

using namespace std;

#define all(x)		(x).begin(), (x).end()
#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;

namespace {
	int variable_example = 1;

}  // namespace

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void Solve(int N, int M) {
	vector<int> vec;
	for (int i = 1; i <= N * M; i++) vec.push_back(i);

	while (int(vec.size()) > N) {
		shuffle(all(vec), rng);
		
		int l = 0, r = int(vec.size()) - 1;
		while (l < r) {
			int mid = (l + r) >> 1;
			vector<int> tmp;
			for (int j = 0; j < mid; j++) tmp.push_back(vec[j]);
			if (Query(tmp)) r = mid;
			else l = mid + 1;
		}

		vector<int> fixed;
		for (int i = 0; i <= l; i++) {
			vector<int> tmp = fixed;
			for (int j = i + 1; j <= l; j++) tmp.push_back(vec[j]);
			if (!Query(tmp)) fixed.push_back(vec[i]);
		}

		for (int e : fixed)
			vec.erase(find(all(vec), e));

		Answer(fixed);
	}

	Answer(vec);
}

Compilation message (stderr)

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

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