Submission #714469

#	Time	Username	Problem	Language	Result	Execution time	Memory
714469		hollwo_pelw	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	1564 ms	1016 KiB

dango3

#include "dango3.h"

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

namespace {

int n, m, f[100000];

}  // namespace

inline vector<int> exclude(vector<int> a, vector<int> b) {
	vector<int> res;
	for (int x : b) f[x] = 1;
	for (int x : a) if (!f[x])
		res.push_back(x);
	for (int x : b) f[x] = 0;
	return res;
}

void solve(vector<int> ids) {
	int sz = ids.size() / n, new_sz = sz / 2;
	// cout << "DIVIDE " << ids.size() << '\n';
	// for (int i : ids) { cout << i << ' '; } cout << '\n';
	if (sz == 1)
		return Answer(ids);
	vector<int> oth;
	for (int x : ids) {
		oth.push_back(x);
		if (Query(exclude(ids, oth)) < new_sz)
			oth.pop_back();
	}
	solve(exclude(ids, oth)), solve(oth);
}

void Solve(int N, int M) {
	n = N, m = M;
	vector<int> ids(n * m);
	iota(ids.begin(), ids.end(), 1);
	solve(ids);
}

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