Submission #547887

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
547887	2022-04-12T01:10:37 Z	racsosabe	Hyper-minimum (IZhO11_hyper)	C++14	0 / 100	961 ms	96132 KB

hyper

#include<bits/stdc++.h>
using namespace::std;

const int N = 35;
const int LOG = 8;

int n;
int m;
int len;
int pos[5];
int a[N][N][N][N];
int ST[N][N][N][N][LOG];

void init(){
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			for(int k = 0; k < n; k++){
				for(int l = 0; l < n; l++){
					ST[i][j][k][l][0] = a[i][j][k][l];
				}
			}
		}
	}
	for(int d = 1, dis = 1; 2 * dis <= m; d++, dis <<= 1){
		assert(d < 8);
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				for(int k = 0; k < n; k++){
					for(int l = 0; l < n; l++){
						vector<int> pos = {i, j, k, l};
						ST[i][j][k][l][d] = INT_MAX;
						for(int mask = 0; mask < 16; mask++){
							for(int at = 0, p = 1; at < 4; at++, p <<= 1){
								if(mask & p) pos[at] += dis;
							}
							ST[i][j][k][l][d] = min(ST[i][j][k][l][d], ST[pos[0]][pos[1]][pos[2]][pos[3]][d - 1]);
							for(int at = 0, p = 1; at < 4; at++, p <<= 1){
								if(mask & p) pos[at] -= dis;
							}
						}
					}
				}
			}
		}
	}
}

int query(int i, int j, int k, int l, int dis, int pot){
	int ans = INT_MAX;
	pos[0] = i;
	pos[1] = j;
	pos[2] = k;
	pos[3] = l;
	for(int mask = 0; mask < 16; mask++){
		for(int at = 0, p = 1; at < 4; at++, p <<= 1){
			if(mask & p) pos[at] += m - dis;
		}
		if(*max_element(pos, pos + 4) >= n) while(true);
		ans = min(ans, ST[pos[0]][pos[1]][pos[2]][pos[3]][pot]);
		for(int at = 0, p = 1; at < 4; at++, p <<= 1){
			if(mask & p) pos[at] -= m - dis;
		}
	}
	return ans;
}

int main(){
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			for(int k = 0; k < n; k++){
				for(int l = 0; l < n; l++){
					scanf("%d", &a[i][j][k][l]);
				}
			}
		}
	}
	init();
	int pot = 0;
	int dis = 1;
	while((dis << 1) <= m){
		dis <<= 1;
		pot++;
	}
	for(int i = 0; i + m - 1 < n; i++){
		for(int j = 0; j + m - 1 < n; j++){
			for(int k = 0; k + m - 1 < n; k++){
				for(int l = 0; l + m - 1 < n; l++){
					printf("%d%c", query(i, j, k, l, dis, pot), " \n"[i + m == n and j + m == n and k + m == n and l + m == n]);
				}
			}
		}
	}
	return 0;
}

Compilation message

hyper.cpp: In function 'int main()':
hyper.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
hyper.cpp:73:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |      scanf("%d", &a[i][j][k][l]);
      |      ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	596 KB	Output is correct
3	Correct	8 ms	2212 KB	Output is correct
4	Correct	6 ms	2212 KB	Output is correct
5	Correct	5 ms	2212 KB	Output is correct
6	Correct	28 ms	6024 KB	Output is correct
7	Correct	32 ms	5884 KB	Output is correct
8	Correct	123 ms	12464 KB	Output is correct
9	Correct	73 ms	14028 KB	Output is correct
10	Correct	134 ms	12468 KB	Output is correct
11	Correct	251 ms	23504 KB	Output is correct
12	Correct	536 ms	38900 KB	Output is correct
13	Correct	638 ms	37752 KB	Output is correct
14	Correct	502 ms	43556 KB	Output is correct
15	Correct	645 ms	59036 KB	Output is correct
16	Runtime error	961 ms	96132 KB	Execution killed with signal 11
17	Halted	0 ms	0 KB	-