Submission #880714

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
880714	2023-11-29T22:23:47 Z	MilosMilutinovic	Hyper-minimum (IZhO11_hyper)	C++14	100 / 100	349 ms	44572 KB

hyper

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<vector<vector<vector<int>>>> a(n, vector<vector<vector<int>>>(n, vector<vector<int>>(n, vector<int>(n))));
  for (int x = 0; x < n; x++) {
    for (int y = 0; y < n; y++) {
      for (int z = 0; z < n; z++) {
        for (int k = 0; k < n; k++) {
          cin >> a[x][y][z][k];
        }
      }
    }
  }  
  vector<vector<vector<vector<int>>>> b(n, vector<vector<vector<int>>>(n, vector<vector<int>>(n, vector<int>(n))));
  for (int x = 0; x < n; x++) {
    for (int y = 0; y < n; y++) {
      for (int z = 0; z < n; z++) {
        deque<int> dq;
        for (int k = n - 1; k >= 0; k--) {
          while (!dq.empty() && dq.front() - k >= m) {
            dq.pop_front();
          }
          while (!dq.empty() && a[x][y][z][dq.back()] >= a[x][y][z][k]) {
            dq.pop_back();
          }
          b[x][y][z][k] = (dq.empty() ? a[x][y][z][k] : a[x][y][z][dq.front()]);
          dq.push_back(k);
        }
      }
    }
  }
  for (int x = 0; x < n; x++) {
    for (int y = 0; y < n; y++) {
      for (int k = 0; k <= n - m; k++) {
        deque<int> dq;
        for (int z = n - 1; z >= 0; z--) {
          while (!dq.empty() && dq.front() - z >= m) {
            dq.pop_front();
          }
          while (!dq.empty() && b[x][y][dq.back()][k] >= b[x][y][z][k]) {
            dq.pop_back();
          }
          a[x][y][z][k] = (dq.empty() ? b[x][y][z][k] : b[x][y][dq.front()][k]);
          dq.push_back(z);
        }
      }
    }
  }
  for (int x = 0; x < n; x++) {
    for (int k = 0; k <= n - m; k++) {
      for (int z = 0; z <= n - m; z++) {
        deque<int> dq;
        for (int y = n - 1; y >= 0; y--) {
          while (!dq.empty() && dq.front() - y >= m) {
            dq.pop_front();
          }
          while (!dq.empty() && a[x][dq.back()][z][k] >= a[x][y][z][k]) {
            dq.pop_back();
          }
          b[x][y][z][k] = (dq.empty() ? a[x][y][z][k] : a[x][dq.front()][z][k]);
          dq.push_back(y);
        }
      }
    }
  }
  for (int k = 0; k <= n - m; k++) {
    for (int z = 0; z <= n - m; z++) {
      for (int y = 0; y <= n - m; y++) {
        deque<int> dq;
        for (int x = n - 1; x >= 0; x--) {
          while (!dq.empty() && dq.front() - x >= m) {
            dq.pop_front();
          }
          while (!dq.empty() && b[dq.back()][y][z][k] >= b[x][y][z][k]) {
            dq.pop_back();
          }
          a[x][y][z][k] = (dq.empty() ? b[x][y][z][k] : b[dq.front()][y][z][k]);
          dq.push_back(x);
        }
      }
    }
  }
  for (int x = 0; x <= n - m; x++) {
    for (int y = 0; y <= n - m; y++) {
      for (int z = 0; z <= n - m; z++) {
        for (int k = 0; k <= n - m; k++) {
          cout << a[x][y][z][k] << " ";
        }
      }
    }
  }
  return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	604 KB	Output is correct
4	Correct	2 ms	604 KB	Output is correct
5	Correct	2 ms	604 KB	Output is correct
6	Correct	8 ms	1628 KB	Output is correct
7	Correct	6 ms	1716 KB	Output is correct
8	Correct	18 ms	3848 KB	Output is correct
9	Correct	34 ms	5712 KB	Output is correct
10	Correct	18 ms	3876 KB	Output is correct
11	Correct	51 ms	9300 KB	Output is correct
12	Correct	103 ms	18044 KB	Output is correct
13	Correct	91 ms	16892 KB	Output is correct
14	Correct	168 ms	22668 KB	Output is correct
15	Correct	256 ms	36104 KB	Output is correct
16	Correct	132 ms	24596 KB	Output is correct
17	Correct	147 ms	25936 KB	Output is correct
18	Correct	349 ms	44572 KB	Output is correct
19	Correct	205 ms	33380 KB	Output is correct
20	Correct	166 ms	31324 KB	Output is correct