Submission #1216307

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216307		PenguinsAreCute	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	405 ms	664 KiB

dango3

#include "dango3.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(12345);
void Solve(int N, int M) {
	vector<bool> used(N*M,0);
	vector<int> perm(N*M);
	iota(perm.begin(),perm.end(),0);
	shuffle(perm.begin(),perm.end(),rng);
	for(int i=0;i<M;i++) {
		vector<int> cur(N, -1);
		auto check = [&used,&cur,&perm](int m) -> bool {
			vector<int> qry;
			int ptr = 0;
			while(qry.size() < m) {
				if(!used[ptr])
					qry.push_back(perm[ptr]+1);
				ptr++;
			}
			for(auto k: cur)
				if(~k)
					qry.push_back(perm[k]+1);
			return Query(qry);
		};
		int prevL = (M - i) * N;
		int g = M - i;
		int k = 0;
		while(2*g+(k<<(k+1)) > g+((k+1)<<(k+1)))
			k++;
		k = (1 << k);
		for(int j=0;j<N;j++) {
			int l = 0, h = prevL;
			while(h > k && check(h - k))
				h -= k;
			l=max(0,h-k);
			while(h - l > 1) {
				int m = (l + h) / 2;
				if(check(m))
					h = m;
				else
					l = m;
			}
			int ptr = -1, cnt = 0;
			while(cnt <= l) {
				if(!used[++ptr])
					cnt++;
			}
			used[ptr] = 1;
			cur[j] = ptr;
			prevL = l;
		}
		for(auto &j: cur)
			j = perm[j] + 1;
		Answer(cur);
	}
}

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