Submission #1216204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216204		siewjh	Super Dango Maker (JOI22_dango3)	C++20	100 / 100	1739 ms	716 KiB

dango3

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

namespace {
	const int MAXM = 25;
	int N, M;
	vector<int> gv[MAXM];
	int query(int l, int r, int xid){
		vector<bool> vb(N * M + 1, 0);
		for (int i = l; i <= r; i++)
			for (int x : gv[i])
				vb[x] = 1;
		vb[xid] = 1;
		vector<int> qv;
		for (int i = N * M; i >= 1; i--)
			if (!vb[i])
				qv.push_back(i);
		return M - Query(qv) == r - l + 1;
	}
}

void Solve(int N, int M) {
	::N = N; ::M = M;
	int grps = 0;
	for (int i = N * M; i >= 1; i--){
		int lo = 0, hi = grps;
		while (lo < hi){
			int m = (lo + hi) >> 1;
			if (query(lo, m, i)) hi = m;
			else lo = m + 1;
		}
		gv[lo].push_back(i);
		if (grps != M - 1 && lo == grps) grps++;
	}
	for (int i = 0; i < M; i++) Answer(gv[i]);
}

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