Submission #951688

#	Time	Username	Problem	Language	Result	Execution time	Memory
951688		GrandTiger1729	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	173 ms	856 KiB

dango3

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

void Solve(int n, int m)
{
	vector<int> idx(n * m);
	iota(idx.begin(), idx.end(), 1);
	vector<vector<int>> ans;
	while (idx.size())
	{
		shuffle(idx.begin(), idx.end(), mt19937(time(0)));
		int rr = -1;
		{
			int l = 0, r = idx.size();
			while (l < r - 1)
			{
				int mid = (l + r) / 2;
				vector<int> qry;
				for (int i = 0; i < mid; i++)
				{
					qry.push_back(idx[i]);
				}
				int res = Query(qry);
				(res == 0 ? l : r) = mid;
			}
			rr = l;
		}
		vector<int> cur, idx2;
		cur.push_back(idx[rr]);
		for (int i = rr - 1; i >= 0; i--)
		{
			vector<int> qry = cur;
			for (int j = 0; j < i; j++)
			{
				qry.push_back(idx[j]);
			}
			int res = Query(qry);
			(res == 0 ? cur : idx2).push_back(idx[i]);
		}
		ans.push_back(cur);
		for (int i = rr + 1; i < idx.size(); i++)
		{
			idx2.push_back(idx[i]);
		}
		swap(idx, idx2);
	}
	for (int i = 0; i < m; i++)
	{
		Answer(ans[i]);
	}
}

Compilation message (stderr)

dango3.cpp: In function 'void Solve(int, int)':
dango3.cpp:42:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for (int i = rr + 1; i < idx.size(); i++)
      |                        ~~^~~~~~~~~~~~

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