Submission #697492

#	Time	Username	Problem	Language	Result	Execution time	Memory
697492		ld_minh4354	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	2577 ms	1068 KiB

dango3

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

#define pb push_back
mt19937_64 rng (chrono :: system_clock :: now().time_since_epoch().count());

void Solve(int n, int m)
{
	int i,cur_n,a[10005],num_taken,id,query_ans;
	bool taken[10005];
	set<int> s;
	
	for (i=1;i<n*m+1;i++) s.insert(i);
	
	for (int w=1;w<m;w++)
	{
		vector<int> ans;
		
		cur_n=0;
		for (auto u:s)
		{
			cur_n++;
			a[cur_n]=u;
		}
		shuffle(a+1,a+cur_n+1,rng);
		
	//	for (i=1;i<cur_n+1;i++) cout<<a[i]<<" ";
	//	cout<<"\n";
		
		for (i=1;i<cur_n+1;i++) taken[i]=false;
		taken[1]=true;
		ans.pb(a[1]);
		s.erase(a[1]);
		num_taken=1;
		
		id=1;
		while (num_taken<n)
		{
			id++;
			vector<int> query_v;
			for (i=1;i<cur_n+1;i++) if (!taken[i] and i!=id) query_v.pb(a[i]);
			
			query_ans=Query(query_v);
			
			if (query_ans==m-w)
			{
				taken[id]=true;
				ans.pb(a[id]);
				num_taken++;
				s.erase(a[id]);
			}
		}
		
//		for (auto u:ans) cout<<u<<" ";
//		cout<<"\n";
		
		Answer(ans);
	}
	
	vector<int> final_ans;
	for (auto u:s) final_ans.pb(u);
	Answer(final_ans);
}

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