Submission #1215427

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215427		emptypringlescan	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	4022 ms	744 KiB

dango3

#include "dango3.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
int n,m;
int max_occ(vector<int> v){
	sort(v.begin(),v.end());
	vector<int> qry;
	for(int i=1; i<=n*m; i++){
		int ind=lower_bound(v.begin(),v.end(),i)-v.begin();
		if(ind<(int)v.size()&&v[ind]==i) continue;
		qry.push_back(i);
	}
	return m-Query(qry);
}
}  // namespace

void Solve(int N, int M) {
	n=N; m=M;
	vector<int> s1[m];
	s1[0]={1};
	for(int i=2; i<=n*m; i++){
		int lo=0,hi=m-1,mid;
		while(lo<hi){
			mid=(lo+hi)/2;
			s1[mid].push_back(i);
			if(max_occ(s1[mid])>1) lo=mid+1;
			else hi=mid;
			s1[mid].pop_back();
		}
		s1[lo].push_back(i);
	}
	for(int i=0; i<m; i++) Answer(s1[i]);
}

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