Submission #523213

#	Time	Username	Problem	Language	Result	Execution time	Memory
523213		Pety	Hyper-minimum (IZhO11_hyper)	C++14	100 / 100	817 ms	42384 KiB

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