Submission #523213

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
523213	2022-02-07T08:06:01 Z	Pety	Hyper-minimum (IZhO11_hyper)	C++14	100 / 100	817 ms	42384 KB

hyper

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int INF = 1e9;
const int MOD = 1e9 + 7;

ifstream fin ("hyper.in");
ofstream fout ("hyper.out");


int n, rmq[9][35][35][35][35], x[35][35][35][35], m, lg2[40];

int query (int i, int j, int k, int l) {
  int i1 = i + m - (1 << lg2[m]);
  int j1 = j + m - (1 << lg2[m]);
  int k1 = k + m - (1 << lg2[m]);
  int l1 = l + m - (1 << lg2[m]);
  int len = lg2[m];
  return min ({
                rmq[len][i][j][k][l],
                rmq[len][i][j][k][l1],
                rmq[len][i][j][k1][l],
                rmq[len][i][j][k1][l1],
                rmq[len][i][j1][k][l],
                rmq[len][i][j1][k][l1],
                rmq[len][i][j1][k1][l],
                rmq[len][i][j1][k1][l1],
                rmq[len][i1][j][k][l],
                rmq[len][i1][j][k][l1],
                rmq[len][i1][j][k1][l],
                rmq[len][i1][j][k1][l1],
                rmq[len][i1][j1][k][l],
                rmq[len][i1][j1][k][l1],
                rmq[len][i1][j1][k1][l],
                rmq[len][i1][j1][k1][l1],
             });
}

int main () 
{
  //ios_base::sync_with_stdio(false);
  //cin.tie(0); cout.tie(0);
  cin >> n >> m;
  for (int i = 2; i <= n; i++)
    lg2[i] = lg2[i / 2] + 1;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      for (int k = 1; k <= n; k++)
        for (int l = 1; l <= n; l++) {
          cin >> x[i][j][k][l];
          rmq[0][i][j][k][l] = x[i][j][k][l];
        }
  for (int len = 1; (1 << len) <= n; len++)
    for (int i = 1; i <= n - (1 << len) + 1; i++)
      for (int j = 1; j <= n - (1 << len) + 1; j++)
        for (int k = 1; k <= n - (1 << len) + 1; k++)
          for (int l = 1; l <= n - (1 << len) + 1; l++) {
              int val = (1 << (len - 1));
              rmq[len][i][j][k][l] = min({
                                      rmq[len - 1][i][j][k][l],
                                      rmq[len - 1][i][j][k][l+val],
                                      rmq[len - 1][i][j][k+val][l],
                                      rmq[len - 1][i][j][k+val][l+val],
                                      rmq[len - 1][i][j+val][k][l],
                                      rmq[len - 1][i][j+val][k][l+val],
                                      rmq[len - 1][i][j+val][k+val][l],
                                      rmq[len - 1][i][j+val][k+val][l+val],
                                      rmq[len - 1][i+val][j][k][l],
                                      rmq[len - 1][i+val][j][k][l+val],
                                      rmq[len - 1][i+val][j][k+val][l],
                                      rmq[len - 1][i+val][j][k+val][l+val],
                                      rmq[len - 1][i+val][j+val][k][l],
                                      rmq[len - 1][i+val][j+val][k][l+val],
                                      rmq[len - 1][i+val][j+val][k+val][l],
                                      rmq[len - 1][i+val][j+val][k+val][l+val],

                                      
                                    });
          }
  for (int i = 1; i <= n - m + 1; i++)
      for (int j = 1; j <= n - m + 1; j++)
        for (int k = 1; k <= n - m + 1; k++)
          for (int l = 1; l <= n - m + 1; l++)
            cout << query(i, j, k, l) << " ";
    
  return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	2 ms	588 KB	Output is correct
3	Correct	5 ms	1996 KB	Output is correct
4	Correct	6 ms	1996 KB	Output is correct
5	Correct	6 ms	2116 KB	Output is correct
6	Correct	25 ms	5100 KB	Output is correct
7	Correct	24 ms	5028 KB	Output is correct
8	Correct	72 ms	8916 KB	Output is correct
9	Correct	92 ms	10692 KB	Output is correct
10	Correct	75 ms	9000 KB	Output is correct
11	Correct	195 ms	14960 KB	Output is correct
12	Correct	367 ms	22236 KB	Output is correct
13	Correct	367 ms	21108 KB	Output is correct
14	Correct	430 ms	27000 KB	Output is correct
15	Correct	660 ms	37568 KB	Output is correct
16	Correct	557 ms	26036 KB	Output is correct
17	Correct	603 ms	27352 KB	Output is correct
18	Correct	817 ms	42384 KB	Output is correct
19	Correct	710 ms	31352 KB	Output is correct
20	Correct	665 ms	29312 KB	Output is correct