Submission #412288

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
412288	2021-05-26T16:41:17 Z	ritul_kr_singh	Hyper-minimum (IZhO11_hyper)	C++17	100 / 100	444 ms	25516 KB

hyper

#pragma GCC optimize("Ofast,unroll-loops")

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int n, m; cin >> n >> m; --m;
	int a[n][n][n][n];
	for(int i=0; i<n; ++i)
		for(int j=0; j<n; ++j)
			for(int k=0; k<n; ++k)
				for(int &l : a[i][j][k]) cin >> l;
	
	for(int i=0; i<n; ++i){
		for(int j=0; j<n; ++j){
			for(int k=0; k<n; ++k){
				deque<int> q;
				for(int l=0; l<n; ++l){
					if(!q.empty() && q.front() < l-m) q.pop_front();
					while(!q.empty() && a[i][j][k][q.back()] >= a[i][j][k][l]) q.pop_back();
					q.push_back(l);
					if(l >= m) a[i][j][k][l-m] = a[i][j][k][q.front()];
				}
			}
			for(int l=0; l<n-m; ++l){
				deque<int> q;
				for(int k=0; k<n; ++k){
					if(!q.empty() && q.front() < k-m) q.pop_front();
					while(!q.empty() && a[i][j][q.back()][l] >= a[i][j][k][l]) q.pop_back();
					q.push_back(k);
					if(k >= m) a[i][j][k-m][l] = a[i][j][q.front()][l];
				}
			}
		}
	}

	for(int k=0; k<n-m; ++k){
		for(int l=0; l<n-m; ++l){
			for(int i=0; i<n; ++i){
				deque<int> q;
				for(int j=0; j<n; ++j){
					if(!q.empty() && q.front() < j-m) q.pop_front();
					while(!q.empty() && a[i][q.back()][k][l] >= a[i][j][k][l]) q.pop_back();
					q.push_back(j);
					if(j >= m) a[i][j-m][k][l] = a[i][q.front()][k][l];
				}
			}
			for(int j=0; j<n-m; ++j){
				deque<int> q;
				for(int i=0; i<n; ++i){
					if(!q.empty() && q.front() < i-m) q.pop_front();
					while(!q.empty() && a[q.back()][j][k][l] >= a[i][j][k][l]) q.pop_back();
					q.push_back(i);
					if(i >= m) a[i-m][j][k][l] = a[q.front()][j][k][l];
				}
			}
		}
	}

	for(int i=0; i<n-m; ++i)
		for(int j=0; j<n-m; ++j)
			for(int k=0; k<n-m; ++k)
				for(int l=0; l<n-m; ++l)
					cout << a[i][j][k][l] << ' ';
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	320 KB	Output is correct
3	Correct	2 ms	448 KB	Output is correct
4	Correct	3 ms	460 KB	Output is correct
5	Correct	3 ms	460 KB	Output is correct
6	Correct	12 ms	1220 KB	Output is correct
7	Correct	9 ms	1100 KB	Output is correct
8	Correct	25 ms	1868 KB	Output is correct
9	Correct	47 ms	3596 KB	Output is correct
10	Correct	28 ms	1928 KB	Output is correct
11	Correct	78 ms	4364 KB	Output is correct
12	Correct	152 ms	8164 KB	Output is correct
13	Correct	121 ms	7012 KB	Output is correct
14	Correct	229 ms	12768 KB	Output is correct
15	Correct	384 ms	21452 KB	Output is correct
16	Correct	184 ms	9952 KB	Output is correct
17	Correct	239 ms	11332 KB	Output is correct
18	Correct	444 ms	25516 KB	Output is correct
19	Correct	283 ms	14532 KB	Output is correct
20	Correct	223 ms	12428 KB	Output is correct