Submission #515758

#	Time	Username	Problem	Language	Result	Execution time	Memory
515758		Be_dos	Hyper-minimum (IZhO11_hyper)	C++17	100 / 100	872 ms	35764 KiB

hyper

#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <unordered_set>
#include <sstream>
#include <cstring>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <random>
#include <cfloat>
#include <chrono>
#include <bitset>
#include <complex>
#include <immintrin.h>
#include <cassert>

struct SuperStack {
    std::vector<std::pair<int32_t, int32_t> > data;

    int32_t get() {
        return data.empty() ? INT32_MAX : data.back().second;
    }

    void push_back(int32_t x) {
        data.emplace_back(x, data.empty() ? x : std::min(data.back().second, x));
    }

    void pop_back() {
        data.pop_back();
    }
};

struct SlidingMin {
    SuperStack left, right;

    int32_t get() {
        return std::min(left.get(), right.get());
    }

    void push_back(int32_t x) {
        right.push_back(x);
    }

    void pop_back() {
        if(left.data.size() == 0) {
            for(int32_t i = right.data.size() / 2; i >= 0; i--)
                left.push_back(right.data[i].first);
            SuperStack right2;
            for(int32_t i = right.data.size() / 2 + 1; i < right.data.size(); i++)
                right2.push_back(right.data[i].first);
            right = right2;
        }
        left.pop_back();
    }
};

int main() {
    int32_t n, m;
    std::cin >> n >> m;

    int32_t**** arr = new int32_t***[n];
    for(int32_t i = 0; i < n; i++) {
        arr[i] = new int32_t**[n];
        for(int32_t j = 0; j < n; j++) {
            arr[i][j] = new int32_t*[n];
            for(int32_t k = 0; k < n; k++) {
                arr[i][j][k] = new int32_t[n];
                for(int32_t p = 0; p < n; p++) {
                    std::cin >> arr[i][j][k][p];
                }
            }
        }
    }

    for(int32_t i = 0; i < n; i++) {
        for(int32_t j = 0; j < n; j++) {
            for(int32_t k = 0; k < n; k++) {
                SlidingMin min;
                for(int32_t p = 0; p < n; p++)
                    if(p + m > n)
                        arr[i][j][k][p] = INT32_MAX;
                    else {
                        if(p == 0)
                            for(int32_t q = 0; q < m; q++)
                                min.push_back(arr[i][j][k][q]);
                        else {
                            min.push_back(arr[i][j][k][p + m - 1]);
                            min.pop_back();
                        }

                        arr[i][j][k][p] = min.get();
                    }
            }
        }
    }

    for(int32_t i = 0; i < n; i++) {
        for(int32_t j = 0; j < n; j++) {
            for(int32_t p = 0; p < n; p++) {
                SlidingMin min;
                for(int32_t k = 0; k < n; k++)
                    if(k + m > n)
                        arr[i][j][k][p] = INT32_MAX;
                    else {
                        if(k == 0)
                            for(int32_t q = 0; q < m; q++)
                                min.push_back(arr[i][j][q][p]);
                        else {
                            min.push_back(arr[i][j][k + m - 1][p]);
                            min.pop_back();
                        }

                        arr[i][j][k][p] = min.get();
                    }
            }
        }
    }

    for(int32_t i = 0; i < n; i++) {
        for(int32_t k = 0; k < n; k++) {
            for(int32_t p = 0; p < n; p++) {
                SlidingMin min;
                for(int32_t j = 0; j < n; j++)
                    if(j + m > n)
                        arr[i][j][k][p] = INT32_MAX;
                    else {
                        if(j == 0)
                            for(int32_t q = 0; q < m; q++)
                                min.push_back(arr[i][q][k][p]);
                        else {
                            min.push_back(arr[i][j + m - 1][k][p]);
                            min.pop_back();
                        }

                        arr[i][j][k][p] = min.get();
                    }
            }
        }
    }

    for(int32_t j = 0; j < n; j++) {
        for(int32_t k = 0; k < n; k++) {
            for(int32_t p = 0; p < n; p++) {
                SlidingMin min;
                for(int32_t i = 0; i < n; i++)
                    if(i + m > n)
                        arr[i][j][k][p] = INT32_MAX;
                    else {
                        if(i == 0)
                            for(int32_t q = 0; q < m; q++)
                                min.push_back(arr[q][j][k][p]);
                        else {
                            min.push_back(arr[i + m - 1][j][k][p]);
                            min.pop_back();
                        }

                        arr[i][j][k][p] = min.get();
                    }
            }
        }
    }

    for(int32_t i = 0; i <= n - m; i++) {
        for(int32_t j = 0; j <= n - m; j++) {
            for(int32_t k = 0; k <= n - m; k++) {
                for(int32_t p = 0; p <= n - m; p++) {
                    std::cout << arr[i][j][k][p] << " ";
                }
            }
        }
    }
    return 0;
}

Compilation message (stderr)

hyper.cpp: In member function 'void SlidingMin::pop_back()':
hyper.cpp:56:58: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |             for(int32_t i = right.data.size() / 2 + 1; i < right.data.size(); i++)
      |                                                        ~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100