Submission #1269128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269128		proofy	Hyper-minimum (IZhO11_hyper)	C++20	100 / 100	526 ms	98424 KiB

hyper

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int n, m;

struct node {
	int value;
	vector<node*> v;
};

void input(node* a, int dimension) {
	if (dimension == 0) {
		cin >> a->value;
		return;
	}

	a->v = vector<node*>(n);
	for (int i = 0; i < n; i++) {
		a->v[i] = new node();
		input(a->v[i], dimension - 1);
	}
}

void output(node* a, int dimension) {
	if (dimension == 0) {
		cout << a->value << " ";
		return;
	}

	for (int i = 0; i + m - 1 < n; i++) 
		output(a->v[i], dimension - 1);
}

void shift(node* a, int dimension) {
	if (dimension == 1) 
		return;

	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++)
			swap(a->v[i]->v[j], a->v[j]->v[i]);
	
	for (int j = 0; j < n; j++)
		shift(a->v[j], dimension - 1);
}

void destroy(node* a) {
	if (!a) 
		return;

	for (int i = 0; i < (int)a->v.size(); i++)
		destroy(a->v[i]);
	delete a;
}

node* solve_1D_only(node* a, int dimension) {
	if (dimension == 1) {
		deque<int> dq;
		node* b = new node();
		b->v = vector<node*>(n);
		for (int i = 0; i < n; i++)
			b->v[i] = new node();

		for (int i = 0; i < n; i++) {
			while (!dq.empty() && dq.front() <= i - m) 
				dq.pop_front();
			while (!dq.empty() && a->v[dq.back()]->value > a->v[i]->value) 
				dq.pop_back();

			dq.push_back(i);

			if (i - m + 1 >= 0) 
				b->v[i - m + 1]->value = a->v[dq.front()]->value;
		}
		destroy(a);
		return b;
	}

	for (int i = 0; i < n; i++) 
		a->v[i] = solve_1D_only(a->v[i], dimension - 1);

	return a;
}

node* solve(node* a, int dimension) {
	if (dimension == 1)
		return solve_1D_only(a, 1);

	for (int i = 0; i < n; i++)
		a->v[i] = solve(a->v[i], dimension - 1);

	shift(a, dimension);

	a = solve_1D_only(a, dimension);
	
	for (int i = 0; i < dimension - 1; i++)
		shift(a, dimension);

	return a;
}

const int D = 4;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	node* a = new node();
	input(a, D);

	a = solve(a, D);
	output(a, D);
}

• Subtask 1: 100 / 100