답안 #38818

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
38818	2018-01-06T17:08:20 Z	Abelyan	최솟값 배열 (IZhO11_hyper)	C++14	100 / 100	683 ms	38624 KB

hyper

#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]);
                                               ^

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	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