Submission #905955

#	Time	Username	Problem	Language	Result	Execution time	Memory
905955		daoquanglinh2007	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	6697 ms	920 KiB

dango3

#include "dango3.h"

#include <bits/stdc++.h>

using namespace std;

int N, M;

int Ask(vector <int> &v){
	sort(v.begin(), v.end());
	vector <int> sv(0);
	int j = 1;
	for (int i : v){
		while (j < i) sv.push_back(j++);
		j++;
	}
	while (j <= N*M) sv.push_back(j++);
	return M-Query(sv);
}

void Solve(int a, int b) {
	N = a, M = b;
	vector <int> g[M+1], v;
	for (int i = 1; i <= M; i++) g[i].clear();
	for (int i = 1; i <= N*M; i++){
		int l = 1, r = M, res = -1;
		while (l <= r){
			int mid = (l+r)/2;
			v.clear();
			for (int j = 1; j <= mid; j++)
				for (int x : g[j]) v.push_back(x);
			v.push_back(i);
			if (Ask(v) <= mid){
				res = mid;
				r = mid-1;
			}
			else l = mid+1;
		}
		g[res].push_back(i);
	}
	for (int i = 1; i <= M; i++) Answer(g[i]);
}

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