Submission #38818

# Submission time Handle Problem Language Result Execution time Memory
38818 2018-01-06T17:08:20 Z Abelyan Hyper-minimum (IZhO11_hyper) C++14
100 / 100
683 ms 38624 KB
#include <bits/stdc++.h>
using namespace std;


class min_queue{
public:
    void del(){
        while (ae>=0) {
            a.pop_back();
            ae--;
        }
        while(be>=0){
            b.pop_back();
            be--;
        }
    }
    void push(int k){
        if (ae!=-1) a.push_back(make_pair(k,min(k,a[ae].second)));
        else a.push_back(make_pair(k,k));
        ae++;
    }
    void pop(){
        if (be==-1){
            b.push_back(make_pair(a[ae].first,a[ae].first));
            ae--;
            a.pop_back();
            be++;
            while(ae>=0){
                b.push_back(make_pair(a[ae].first,min(a[ae].first,b[be].second)));
                a.pop_back();
                ae--;
                be++;
            }
        }
        b.pop_back();
        be--;
    }
    int mn(){
        int am=ae>=0?a[ae].second:INT_MAX;
        int bm=be>=0?b[be].second:INT_MAX;
        return min(am,bm);
    }
    min_queue(){
        ae=-1;
        be=-1;
    }
private:
    vector <pair<int,int > > a;
    vector <pair<int,int > > b;
    int ae,be;
};

const int N=37;

min_queue q;
int a[N][N][N][N];
int b1[N][N][N][N];
int b2[N][N][N][N];
int b3[N][N][N][N];
int b4[N][N][N][N];

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            for(int k=1;k<=n;++k)
                for(int l=1;l<=n;++l)
                    scanf("%d",&a[i][j][k][l]);
    for(int j=1;j<=n;++j)
        for(int k=1;k<=n;++k)
            for(int l=1;l<=n;++l){
                q.del();
                for(int i=1;i<m;++i){
                    q.push(a[i][j][k][l]);
                }
                for(int i=m;i<=n;++i){
                    q.push(a[i][j][k][l]);
                    b1[i-m+1][j][k][l]=q.mn();
                    q.pop();
                }
            }
    for(int i=1;i<=n-m+1;i++)
        for(int k=1;k<=n;++k)
            for(int l=1;l<=n;++l){
                q.del();
                for(int j=1;j<m;++j){
                    q.push(b1[i][j][k][l]);
                }
                for(int j=m;j<=n;++j){
                    q.push(b1[i][j][k][l]);
                    b2[i][j-m+1][k][l]=q.mn();
                    q.pop();
                }
            }
    for(int i=1;i<=n-m+1;++i)
        for(int j=1;j<=n-m+1;++j)
            for(int l=1;l<=n;++l){
                q.del();
                for(int k=1;k<m;++k){
                    q.push(b2[i][j][k][l]);
                }
                for(int k=m;k<=n;++k){
                    q.push(b2[i][j][k][l]);
                    b3[i][j][k-m+1][l]=q.mn();
                    q.pop();
                }
            }
    for(int i=1;i<=n-m+1;++i)
        for(int j=1;j<=n-m+1;++j)
            for(int k=1;k<=n-m+1;++k){
                q.del();
                for(int l=1;l<m;++l){
                    q.push(b3[i][j][k][l]);
                }
                for(int l=m;l<=n;++l){
                    q.push(b3[i][j][k][l]);
                    b4[i][j][k][l-m+1]=q.mn();
                    q.pop();
                }
            }
    for(int i=1;i<=n-m+1;++i)
        for(int j=1;j<=n-m+1;++j)
            for(int k=1;k<=n-m+1;++k)
                for(int l=1;l<=n-m+1;++l){
                    printf("%d ",b4[i][j][k][l]);
                }
    return 0;
}

Compilation message

hyper.cpp: In function 'int main()':
hyper.cpp:70:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                     scanf("%d",&a[i][j][k][l]);
                                               ^
# Verdict Execution time Memory Grader output
1 Correct 0 ms 38624 KB Output is correct
2 Correct 0 ms 38624 KB Output is correct
3 Correct 0 ms 38624 KB Output is correct
4 Correct 3 ms 38624 KB Output is correct
5 Correct 3 ms 38624 KB Output is correct
6 Correct 26 ms 38624 KB Output is correct
7 Correct 13 ms 38624 KB Output is correct
8 Correct 46 ms 38624 KB Output is correct
9 Correct 69 ms 38624 KB Output is correct
10 Correct 69 ms 38624 KB Output is correct
11 Correct 149 ms 38624 KB Output is correct
12 Correct 263 ms 38624 KB Output is correct
13 Correct 176 ms 38624 KB Output is correct
14 Correct 376 ms 38624 KB Output is correct
15 Correct 576 ms 38624 KB Output is correct
16 Correct 276 ms 38624 KB Output is correct
17 Correct 409 ms 38624 KB Output is correct
18 Correct 683 ms 38624 KB Output is correct
19 Correct 529 ms 38624 KB Output is correct
20 Correct 416 ms 38624 KB Output is correct