Submission #331109

#	Time	Username	Problem	Language	Result	Execution time	Memory
331109		AlexLuchianov	Hyper-minimum (IZhO11_hyper)	C++14	100 / 100	464 ms	36588 KiB

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 / 100