oj.uz

답안 #848282

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
848282 2023-09-12T01:21:59 Z wakandaaa 최솟값 배열 (IZhO11_hyper) C++17
0 / 100
 412 ms 71468 KB 
#include <bits/stdc++.h>

using namespace std;

#define file ""

#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()

#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1LL << (x))
#define popcount __builtin_popcountll

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
    return l + rd() % (r - l + 1);
}

const int N = 40;
const int mod = (int)1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int oo = 2e9;
const long long ooo = 1e18;

template<class X, class Y> bool mini(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maxi(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}
void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

int n, m;
int f[N][N][N][N][7];
int lg2[N];


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

    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);

    for (int i = 2; i < N; ++i) lg2[i] = lg2[i >> 1] + 1;

	cin >> n >> m;
	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 >> f[i][j][k][l][0];

	for (int s = 1; s <= 6; ++s) {
		int x = bit(s - 1);
		int y = n - bit(s) + 1;
		for (int i = 1; i <= y; ++i) 
			for (int j = 1; j <= y; ++j) 
				for (int k = 1; k <= y; ++k) 
					for (int l = 1; l <= y; ++l) {
						for (int mask = 0; mask < bit(4); ++mask) {
							int ni = i + getbit(mask, 0) * x;
							int nj = j + getbit(mask, 1) * x;
							int nk = k + getbit(mask, 2) * x;
							int nl = l + getbit(mask, 3) * x;
							mini(f[i][j][k][l][s], f[ni][nj][nk][nl][s - 1]);
						}
		}
	}

	auto get = [&] (int i, int j, int k, int l, int ri, int rj, int rk, int rl) {
		int res = oo;
		int s = lg2[m];
		for (int mask = 0; mask < bit(4); ++mask) {
			int ii = getbit(mask, 0) ? ri - bit(s) + 1 : i;
			int jj = getbit(mask, 1) ? rj - bit(s) + 1 : j;
			int kk = getbit(mask, 2) ? rk - bit(s) + 1 : k;
			int ll = getbit(mask, 3) ? rl - bit(s) + 1 : l;
			mini(res, f[ii][jj][kk][ll][s]);
		}
		return res;
	};

	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 << get(i, j, k, l, i + m - 1, j + m - 1, k + m - 1, l + m - 1) << ' ';

    return 0;
}

/*
3 2
3 1 4 -4 0 4 0 0 -3 0 -2 -5 5 3 5 -4
4 -3 -5 -4 -4 5 -1 0 -3 -2 -1 2 -5 -5
-1 1 1 -4 3 5 3 -3 -3 3 0 1 4 -1 -2 3
-2 5 4 -1 -5 3 -4 0 -3 -1 3 -1 4 4 -1
-5 -3 4 -4 5 1 5 -4 3 2 2 -2 -2 4 2
-4 -3 1 3 1

-5 -5 -4 -3 -5 -5 -4 -5 -5 -5 -5 -5 -4 -5 -4 -5
*/

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 4 ms 18780 KB Output is correct
4 Correct 4 ms 18776 KB Output is correct
5 Correct 5 ms 18780 KB Output is correct
6 Correct 14 ms 29196 KB Output is correct
7 Correct 13 ms 29016 KB Output is correct
8 Correct 36 ms 37212 KB Output is correct
9 Correct 57 ms 39060 KB Output is correct
10 Correct 36 ms 37380 KB Output is correct
11 Correct 95 ms 46076 KB Output is correct
12 Correct 198 ms 56912 KB Output is correct
13 Correct 190 ms 55632 KB Output is correct
14 Correct 262 ms 61680 KB Output is correct
15 Incorrect 412 ms 71468 KB Output isn't correct
16 Halted 0 ms 0 KB -