Submission #1323434

#TimeUsernameProblemLanguageResultExecution timeMemory
1323434Jawad_Akbar_JJHyper-minimum (IZhO11_hyper)C++20
0 / 100
205 ms33236 KiB
#include <iostream>
#include <deque>

using namespace std;
const int N = 35;
int n, m;
int c[N][N];

void solve(int a[][N], int b[][N]){
	for (int i=1;i<=n;i++){
		deque<int> d;
		for (int j=n;j>=1;j--){
			while (d.size() > 0 and a[i][d.back()] > a[i][j])
				d.pop_back();
			if (d.size() > 0 and d.front() >= j + m)
				d.pop_front();
			d.push_back(j);
			c[i][j] = a[i][d.front()];
		}
	}
	for (int j=1;j<=n;j++){
		deque<int> d;
		for (int i=n;i>=1;i--){
			while (d.size() > 0 and c[d.back()][j] > c[i][j])
				d.pop_back();
			if (d.size() > 0 and d.front() >= i + m)
				d.pop_front();
			d.push_back(i);
			b[i][j] = c[d.front()][j];
		}
	}
}

int a[N][N][N][N];
int b[N][N][N][N];
int e[N][N][N][N];
int f[N][N][N][N];

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin>>n>>m;

	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++)
			for (int k=1;k<=n;k++)
				for (int l=1;l<=n;l++)
					cin>>a[i][j][k][l];
	}

	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++)
			solve(a[i][j], b[i][j]);
	}

	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			for (int k=1;k<=n;k++)
				for (int l=1;l<=n;l++)
					e[k][l][i][j] = b[i][j][k][l];
		}
	}
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++)
			solve(e[i][j], f[i][j]);
	}

	for (int i=1;i<=n-m+1;i++){
		for (int j=1;j<=n-m+1;j++){
			for (int k=1;k<=n-m+1;k++)
				for (int l=1;l<=n-m+1;l++)
					cout<<f[k][l][i][j]<<' ';
		}
	}
	cout<<'\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...