답안 #572246

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
572246	2022-06-04T06:09:58 Z	SSRS	최솟값 배열 (IZhO11_hyper)	C++14	100 / 100	790 ms	22320 KB

hyper

#include <bits/stdc++.h>
using namespace std;
vector<int> slide_min(vector<int> &A, int M){
  int N = A.size();
  deque<int> dq;
  vector<int> ans(N - M + 1);
  for (int i = 0; i < N; i++){
    while (!dq.empty()){
      if (A[dq.back()] >= A[i]){
        dq.pop_back();
      } else {
        break;
      }
    }
    dq.push_back(i);
    if (i >= M - 1){
      ans[i - M + 1] = A[dq.front()];
      if (dq.front() == i - M + 1){
        dq.pop_front();
      }
    }
  }
  return ans;
}
int main(){
  int N, M;
  cin >> N >> M;
  vector<vector<vector<vector<int>>>> X(N, vector<vector<vector<int>>>(N, vector<vector<int>>(N, vector<int>(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 >> X[i][j][k][l];
        }
      }
    }
  }
  for (int i = 0; i < N; i++){
    for (int j = 0; j < N; j++){
      for (int k = 0; k < N; k++){
        vector<int> A = X[i][j][k];
        vector<int> B = slide_min(A, M);
        for (int l = 0; l <= N - M; l++){
          X[i][j][k][l] = B[l];
        }
      }
    }
  }
  for (int i = 0; i < N; i++){
    for (int j = 0; j < N; j++){
      for (int k = 0; k <= N - M; k++){
        vector<int> A(N);
        for (int l = 0; l < N; l++){
          A[l] = X[i][j][l][k];
        }
        vector<int> B = slide_min(A, M);
        for (int l = 0; l <= N - M; l++){
          X[i][j][l][k] = B[l];
        }
      }
    }
  }
  for (int i = 0; i < N; i++){
    for (int j = 0; j <= N - M; j++){
      for (int k = 0; k <= N - M; k++){
        vector<int> A(N);
        for (int l = 0; l < N; l++){
          A[l] = X[i][l][j][k];
        }
        vector<int> B = slide_min(A, M);
        for (int l = 0; l <= N - M; l++){
          X[i][l][j][k] = B[l];
        }
      }
    }
  }
  for (int i = 0; i <= N - M; i++){
    for (int j = 0; j <= N - M; j++){
      for (int k = 0; k <= N - M; k++){
        vector<int> A(N);
        for (int l = 0; l < N; l++){
          A[l] = X[l][i][j][k];
        }
        vector<int> B = slide_min(A, M);
        for (int l = 0; l <= N - M; l++){
          X[l][i][j][k] = B[l];
        }
      }
    }
  }
  for (int i = 0; i <= N - M; i++){
    for (int j = 0; j <= N - M; j++){
      for (int k = 0; k <= N - M; k++){
        for (int l = 0; l <= N - M; l++){
          cout << X[i][j][k][l];
          if (i < N - M || j < N - M || k < N - M || l < N - M){
            cout << ' ';
          }
        }
      }
    }
  }
  cout << endl;
}

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	296 KB	Output is correct
3	Correct	5 ms	468 KB	Output is correct
4	Correct	5 ms	436 KB	Output is correct
5	Correct	7 ms	436 KB	Output is correct
6	Correct	27 ms	1316 KB	Output is correct
7	Correct	28 ms	1156 KB	Output is correct
8	Correct	68 ms	2120 KB	Output is correct
9	Correct	91 ms	3700 KB	Output is correct
10	Correct	66 ms	2172 KB	Output is correct
11	Correct	187 ms	3948 KB	Output is correct
12	Correct	359 ms	6460 KB	Output is correct
13	Correct	345 ms	5312 KB	Output is correct
14	Correct	447 ms	11064 KB	Output is correct
15	Correct	644 ms	18824 KB	Output is correct
16	Correct	499 ms	7244 KB	Output is correct
17	Correct	521 ms	8656 KB	Output is correct
18	Correct	790 ms	22320 KB	Output is correct
19	Correct	672 ms	11212 KB	Output is correct
20	Correct	587 ms	9188 KB	Output is correct