Submission #617437

#	Time	Username	Problem	Language	Result	Execution time	Memory
617437		patrikpavic2	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	722 ms	764 KiB

dango3

#include "dango3.h"
#include <vector>
#include <algorithm>
#include <cstdio>

#define PB push_back

using namespace std;

typedef vector < int > vi;

namespace {

const int MAXN = 1e6 + 500;

int sve[MAXN];

void divnconq(vi v, vi sig, int k){
	if(k == 1){ 
		for(int &x : sig) v.PB(x);
		Answer(v); return; 
	}
	int c = k / 2, n = (int)(v.size() + sig.size()) / k;
	vi kog = sig, ost;
	int ret = 0;
	for(int j = 16;j >= 0;j--){
		if(ret + (1 << j) < (int)v.size()){
			for(int k = 0;k < (1 << j);k++) kog.PB(v[ret + k]);
			if(Query(kog) >= c)
				for(int k = 0;k < (1 << j);k++) kog.pop_back();
			else
				ret += (1 << j);
		}
	}
	kog.PB(v[ret]);
	for(int &x : v) sve[x] = 1;
	for(int &x : kog) sve[x] = 0;
	for(int &x : v)
		if(sve[x]) ost.PB(x);
	vi vis;
	while((int)kog.size() > c * n){
		int st = kog.back();
		kog.pop_back();
		if(Query(kog) < c)
			kog.insert(kog.begin(), st);
		else
			vis.PB(st);
	}
	divnconq(kog, {}, c);
	divnconq(ost, vis, k - c);
}

}

void Solve(int n, int m) {
	vi poc;
	for(int i = 1;i <= n * m;i++)
		poc.PB(i);
	divnconq(poc, {}, m);
}

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