Submission #331109

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
331109	2020-11-27T11:38:34 Z	AlexLuchianov	Hyper-minimum (IZhO11_hyper)	C++14	100 / 100	464 ms	36588 KB

hyper

#include <iostream>
#include <vector>
#include <cassert>
#include <cmath>
#include <algorithm>
#include <deque>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

#define vec std::vector

class Dqmin{
private:
  std::deque<std::pair<int,int>> dqmin;
public:
  Dqmin() {

  }
  void _insert(std::pair<int,int> val) {
    while(0 < dqmin.size() && val < dqmin.back())
      dqmin.pop_back();
    dqmin.push_back(val);
  }
  int extract(int lim) {
    while(dqmin.front().second <= lim)
      dqmin.pop_front();
    return dqmin.front().first;
  }
};

int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);

  int n, m;
  std::cin >> n >> m;
  vec<vec<vec<vec<int>>>> mat;
  mat.resize(n);
  for(int i = 0; i < n; i++) {
    mat[i].resize(n);
    for(int j = 0; j < n; j++) {
      mat[i][j].resize(n);
      for(int k = 0; k < n; k++) {
        mat[i][j][k].resize(n);
        for(int h = 0; h < n; h++)
          std::cin >> mat[i][j][k][h];
      }
    }
  }
  for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
      for(int k = 0; k < n; k++) {
        Dqmin dqmin;
        for(int h = 0; h < n; h++) {
          dqmin._insert({mat[i][j][k][h], h});
          if(m - 1 <= h)
            mat[i][j][k][h - m + 1] = dqmin.extract(h - m);
        }
      }
  for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
      for(int h = 0; h < n - m + 1; h++) {
        Dqmin dqmin;
        for(int k = 0; k < n; k++) {
          dqmin._insert({mat[i][j][k][h], k});
          if(m - 1 <= k)
            mat[i][j][k - m + 1][h] = dqmin.extract(k - m);
        }
      }
  for(int i = 0; i < n; i++) 
    for(int k = 0; k < n - m + 1; k++)
      for(int h = 0; h < n - m + 1; h++) {
        Dqmin dqmin;
        for(int j = 0; j < n; j++) {
          dqmin._insert({mat[i][j][k][h], j});
          if(m - 1 <= j)
            mat[i][j - m + 1][k][h] = dqmin.extract(j - m);
        }
      }
  for(int j = 0; j < n - m + 1; j++)
    for(int k = 0; k < n - m + 1; k++)
      for(int h = 0; h < n - m + 1; h++) { 
        Dqmin dqmin;
        for(int i = 0; i < n; i++) {
          dqmin._insert({mat[i][j][k][h], i});
          if(m - 1 <= i)
            mat[i - m + 1][j][k][h] = dqmin.extract(i - m);
        }
      }
  for(int i = 0; i < n - m + 1; i++)
    for(int j = 0; j < n - m + 1; j++)
      for(int k = 0; k < n - m + 1; k++)
        for(int h = 0; h < n - m + 1; h++)
          std::cout << mat[i][j][k][h] << " ";
  return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	2 ms	492 KB	Output is correct
4	Correct	3 ms	492 KB	Output is correct
5	Correct	3 ms	620 KB	Output is correct
6	Correct	12 ms	1388 KB	Output is correct
7	Correct	10 ms	1260 KB	Output is correct
8	Correct	26 ms	2924 KB	Output is correct
9	Correct	57 ms	4716 KB	Output is correct
10	Correct	29 ms	3052 KB	Output is correct
11	Correct	80 ms	7148 KB	Output is correct
12	Correct	168 ms	13804 KB	Output is correct
13	Correct	127 ms	12780 KB	Output is correct
14	Correct	234 ms	18540 KB	Output is correct
15	Correct	392 ms	29932 KB	Output is correct
16	Correct	185 ms	18412 KB	Output is correct
17	Correct	269 ms	19820 KB	Output is correct
18	Correct	464 ms	36588 KB	Output is correct
19	Correct	299 ms	25600 KB	Output is correct
20	Correct	228 ms	23552 KB	Output is correct