Submission #961332

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
961332	2024-04-11T20:23:34 Z	biank	Hyper-minimum (IZhO11_hyper)	C++14	100 / 100	340 ms	41556 KB

hyper

#include <bits/stdc++.h>

using namespace std;

#define sz(x) int(x.size())

using vi = vector<int>;
using vvi = vector<vi>;

vi minimumSlidingWindow(vi &v, int k) {
    vi m;
    deque<int> dq;
    for (int i = 0; i < sz(v); i++) {
        while (!dq.empty() && v[dq.back()] >= v[i]) {
            dq.pop_back();
        }
        dq.push_back(i);
        if (i >= k && dq.front() == i - k) dq.pop_front();
        if (i >= k - 1) m.push_back(v[dq.front()]);
    }
    return m;
}

void apply(vector<vector<vvi>> &v, int m) {
    for (int i = 0; i < sz(v); i++) {
        for (int j = 0; j < sz(v[i]); j++) {
            for (int k = 0; k < sz(v[i][j]); k++) {
                v[i][j][k] = minimumSlidingWindow(v[i][j][k], m);
            }
        }
    }
}

vector<vector<vvi>> transpose(vector<vector<vvi>> &v) {//i -> j, j -> k, k -> l, l -> i
    int A = sz(v), B = sz(v[0]), C = sz(v[0][0]), D = sz(v[0][0][0]);
    vector<vector<vvi>> t(B, vector<vvi>(C, vvi(D, vi(A))));
    for (int i = 0; i < A; i++) {
        for (int j = 0; j < B; j++) {
            for (int k = 0; k < C; k++) {
                for (int l = 0; l < D; l++) {
                    t[j][k][l][i] = v[i][j][k][l];
                }
            }
        }
    }
    return t;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n, m;
    cin >> n >> m;
    vector<vector<vvi>> v(n, vector<vvi>(n, vvi(n, vi(n))));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                for (int l = 0; l < n; l++) {
                    cin >> v[i][j][k][l];
                }
            }
        }
    }
    for (int i = 0; i < 4; i++) {
        apply(v, m);
        v = transpose(v);
    }
    n -= m - 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                for (int l = 0; l < n; l++) {
                    cout << v[i][j][k][l] << ' ';
                }
            }
        }
    }
    
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	604 KB	Output is correct
4	Correct	2 ms	724 KB	Output is correct
5	Correct	2 ms	604 KB	Output is correct
6	Correct	11 ms	1628 KB	Output is correct
7	Correct	7 ms	1368 KB	Output is correct
8	Correct	17 ms	2896 KB	Output is correct
9	Correct	43 ms	5968 KB	Output is correct
10	Correct	20 ms	3112 KB	Output is correct
11	Correct	56 ms	7900 KB	Output is correct
12	Correct	116 ms	15752 KB	Output is correct
13	Correct	88 ms	12884 KB	Output is correct
14	Correct	176 ms	22476 KB	Output is correct
15	Correct	268 ms	29660 KB	Output is correct
16	Correct	129 ms	18468 KB	Output is correct
17	Correct	179 ms	21996 KB	Output is correct
18	Correct	340 ms	41556 KB	Output is correct
19	Correct	219 ms	28140 KB	Output is correct
20	Correct	156 ms	23636 KB	Output is correct