답안 #523199

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
523199	2022-02-07T07:50:13 Z	redstonegamer22	최솟값 배열 (IZhO11_hyper)	C++17	100 / 100	1014 ms	48756 KB

hyper

#include <bits/stdc++.h>

using namespace std;

const int NMAX = 40;

int x[NMAX][NMAX][NMAX][NMAX];
int y[NMAX][NMAX][NMAX][NMAX];

void print_x(ostream& out, int n) {
    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++) {
                    out << x[i][j][k][l] << " ";
                }
            }
        }
    }
    out << endl;
}

int main() {
    assert(NMAX * NMAX * NMAX * NMAX > 1500000);

    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++)
                    cin >> x[i][j][k][l];

    /// Compress l
    memset(y, 0x7F, sizeof(y));
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            for(int k = 1; k <= n; k++) {
                multiset<int> ms;

                for(int l = 1; l <= n; l++) {
                    ms.insert(x[i][j][k][l]);
                    if(l - m >= 1) ms.erase(ms.find(x[i][j][k][l - m]));

                    if(l - m + 1 >= 1) y[i][j][k][l - m + 1] = *(ms.begin());
                }
            }
        }
    }
    memcpy(x, y, sizeof(x));

#ifdef LOCAL
    print_x(cerr, n);
#endif // LOCAL

    /// Compress k
    memset(y, 0x7F, sizeof(y));
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            for(int l = 1; l <= n; l++) {
                multiset<int> ms;

                for(int k = 1; k <= n; k++) {
                    ms.insert(x[i][j][k][l]);
                    if(k - m >= 1) ms.erase(ms.find(x[i][j][k - m][l]));

                    if(k - m + 1 >= 1) y[i][j][k - m + 1][l] = *(ms.begin());
                }
            }
        }
    }
    memcpy(x, y, sizeof(x));

#ifdef LOCAL
    print_x(cerr, n);
#endif // LOCAL

    /// Compress j
    memset(y, 0x7F, sizeof(y));
    for(int i = 1; i <= n; i++) {
        for(int k = 1; k <= n; k++) {
            for(int l = 1; l <= n; l++) {
                multiset<int> ms;

                for(int j = 1; j <= n; j++) {
                    ms.insert(x[i][j][k][l]);
                    if(j - m >= 1) ms.erase(ms.find(x[i][j - m][k][l]));

                    if(j - m + 1 >= 1) y[i][j - m + 1][k][l] = *(ms.begin());
                }
            }
        }
    }
    memcpy(x, y, sizeof(x));

#ifdef LOCAL
    print_x(cerr, n);
#endif // LOCAL

    /// Compress i
    memset(y, 0x7F, sizeof(y));
    for(int j = 1; j <= n; j++) {
        for(int k = 1; k <= n; k++) {
            for(int l = 1; l <= n; l++) {
                multiset<int> ms;

                for(int i = 1; i <= n; i++) {
                    ms.insert(x[i][j][k][l]);
                    if(i - m >= 1) ms.erase(ms.find(x[i - m][j][k][l]));

                    if(i - m + 1 >= 1) y[i - m + 1][j][k][l] = *(ms.begin());
                }
            }
        }
    }
    memcpy(x, y, sizeof(x));

#ifdef LOCAL
    print_x(cerr, n);
#endif // LOCAL

    print_x(cout, n - m + 1);
}

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	20300 KB	Output is correct
2	Correct	16 ms	20220 KB	Output is correct
3	Correct	22 ms	20372 KB	Output is correct
4	Correct	24 ms	20344 KB	Output is correct
5	Correct	27 ms	20408 KB	Output is correct
6	Correct	50 ms	20932 KB	Output is correct
7	Correct	49 ms	20768 KB	Output is correct
8	Correct	110 ms	21944 KB	Output is correct
9	Correct	116 ms	23608 KB	Output is correct
10	Correct	117 ms	21956 KB	Output is correct
11	Correct	272 ms	24904 KB	Output is correct
12	Correct	602 ms	29636 KB	Output is correct
13	Correct	505 ms	28680 KB	Output is correct
14	Correct	584 ms	34452 KB	Output is correct
15	Correct	823 ms	44040 KB	Output is correct
16	Correct	754 ms	32536 KB	Output is correct
17	Correct	790 ms	33928 KB	Output is correct
18	Correct	998 ms	48756 KB	Output is correct
19	Correct	1014 ms	37776 KB	Output is correct
20	Correct	882 ms	35716 KB	Output is correct