Submission #547891

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
547891	2022-04-12T01:17:44 Z	racsosabe	Hyper-minimum (IZhO11_hyper)	C++14	100 / 100	784 ms	66180 KB

hyper

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

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

int n;
int m;
int len;
int pot;
int dis;
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 + 2 * dis - 1 < n; i++){
			for(int j = 0; j + 2 * dis - 1 < n; j++){
				for(int k = 0; k + 2 * dis - 1 < n; k++){
					for(int l = 0; l + 2 * dis - 1 < n; l++){
						pos[0] = i;
						pos[1] = j;
						pos[2] = k;
						pos[3] = 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 ans = 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] += 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();
	pot = 0;
	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++){
					pos[0] = i;
					pos[1] = j;
					pos[2] = k;
					pos[3] = l;
					printf("%d%c", query(), " \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:69:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
hyper.cpp:74:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |      scanf("%d", &a[i][j][k][l]);
      |      ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.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	6 ms	2132 KB	Output is correct
4	Correct	6 ms	2132 KB	Output is correct
5	Correct	7 ms	2196 KB	Output is correct
6	Correct	24 ms	6008 KB	Output is correct
7	Correct	19 ms	5892 KB	Output is correct
8	Correct	61 ms	12528 KB	Output is correct
9	Correct	69 ms	14032 KB	Output is correct
10	Correct	60 ms	12436 KB	Output is correct
11	Correct	203 ms	23484 KB	Output is correct
12	Correct	344 ms	38904 KB	Output is correct
13	Correct	340 ms	37640 KB	Output is correct
14	Correct	440 ms	43588 KB	Output is correct
15	Correct	660 ms	59076 KB	Output is correct
16	Correct	516 ms	47564 KB	Output is correct
17	Correct	514 ms	48808 KB	Output is correct
18	Correct	784 ms	66180 KB	Output is correct
19	Correct	657 ms	55184 KB	Output is correct
20	Correct	667 ms	53136 KB	Output is correct