#include <bits/stdc++.h>
using namespace std;
const int N = 16; //TODO: Fix bound
const int LG = 5;
const int INF = (1e9) + 7;
int n,m,a[N][N][N][N],ans[N][N][N][N];
int rmq[N][N][N][N][LG][LG][LG][LG];
int lg;
void build() {
int i1,i2,i3,i4,j1,j2,j3,j4;
for(j1=0;(1<<j1)<=n;j1++) for(j2=0;(1<<j2)<=n;j2++) for(j3=0;(1<<j3)<=n;j3++) for(j4=0;(1<<j4)<=n;j4++) {
for(i1=1;i1+(1<<j1)-1<=n;i1++) for(i2=1;i2+(1<<j2)-1<=n;i2++) for(i3=1;i3+(1<<j3)-1<=n;i3++) for(i4=1;i4+(1<<j4)-1<=n;i4++) {
//fprintf(stderr, "{ %d, %d, %d, %d } / { %d, %d, %d, %d }", i1, i2, i3, i4, j1, j2, j3, j4);
//if(j1==0 && j2==0 && j3==0 && j4==0) rmq[i1][i2][i3][i4][j1][j2][j3][j4]=a[i1][i2][i3][i4];
if(j1>0) {
rmq[i1][i2][i3][i4][j1][j2][j3][j4]=min(
rmq[i1][i2][i3][i4][j1-1][j2][j3][j4],
rmq[i1+(1<<(j1-1))][i2][i3][i4][j1-1][j2][j3][j4]
);
}
else if(j2>0) {
rmq[i1][i2][i3][i4][j1][j2][j3][j4]=min(
rmq[i1][i2][i3][i4][j1][j2-1][j3][j4],
rmq[i1][i2+(1<<(j2-1))][i3][i4][j1][j2-1][j3][j4]
);
}
else if(j3>0) {
rmq[i1][i2][i3][i4][j1][j2][j3][j4]=min(
rmq[i1][i2][i3][i4][j1][j2][j3-1][j4],
rmq[i1][i2][i3+(1<<(j3-1))][i4][j1][j2][j3-1][j4]
);
}
else if(j4>0) {
rmq[i1][i2][i3][i4][j1][j2][j3][j4]=min(
rmq[i1][i2][i3][i4][j1][j2][j3][j4-1],
rmq[i1][i2][i3][i4+(1<<(j4-1))][j1][j2][j3][j4-1]
);
}
else rmq[i1][i2][i3][i4][j1][j2][j3][j4]=a[i1][i2][i3][i4];
//fprintf(stderr, " { %d }\n", rmq[i1][i2][i3][i4][j1][j2][j3][j4]);
}
}
}
int get(int start, int f) {
if(f==0) return start;
else return start+m-(1<<lg);
}
int query(int i1, int i2, int i3, int i4) {
int f1,f2,f3,f4,ans=INF;
for(f1=0;f1<=1;f1++) for(f2=0;f2<=1;f2++) for(f3=0;f3<=1;f3++) for(f4=0;f4<=1;f4++) {
ans=min(ans,rmq[get(i1,f1)][get(i2,f2)][get(i3,f3)][get(i4,f4)][lg][lg][lg][lg]);
}
return ans;
}
int main() {
int i,j,z,k;
scanf("%d %d", &n, &m);
for(i=1;i<=n;i++) for(j=1;j<=n;j++) for(z=1;z<=n;z++) for(k=1;k<=n;k++) scanf("%d", &a[i][j][z][k]);
//fprintf(stderr, "Input read\n");
build();
lg=log2(m);
//fprintf(stderr, "RMQ table built\n");
for(i=1;i<=n-m+1;i++) for(j=1;j<=n-m+1;j++) for(z=1;z<=n-m+1;z++) for(k=1;k<=n-m+1;k++) {
ans[i][j][z][k]=query(i,j,z,k);
if(i>1 || j>1 || z>1 || k>1) printf(" ");
printf("%d", ans[i][j][z][k]);
}
printf("\n");
return 0;
}
Compilation message
hyper.cpp: In function 'int main()':
hyper.cpp:65:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
^
hyper.cpp:66:104: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(i=1;i<=n;i++) for(j=1;j<=n;j++) for(z=1;z<=n;z++) for(k=1;k<=n;k++) scanf("%d", &a[i][j][z][k]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
162548 KB |
Output is correct |
| 2 |
Correct |
0 ms |
162548 KB |
Output is correct |
| 3 |
Correct |
19 ms |
162548 KB |
Output is correct |
| 4 |
Correct |
19 ms |
162548 KB |
Output is correct |
| 5 |
Correct |
33 ms |
162548 KB |
Output is correct |
| 6 |
Correct |
173 ms |
162548 KB |
Output is correct |
| 7 |
Correct |
156 ms |
162548 KB |
Output is correct |
| 8 |
Incorrect |
26 ms |
162548 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
