oj.uz

Submission #24411

# Submission time Handle Problem Language Result Execution time Memory
24411 2017-06-07T10:37:14 Z Extazy Hyper-minimum (IZhO11_hyper) C++14
0 / 100
 0 ms 1860 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 20; //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]);
                                                                                                        ^

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1860 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -