oj.uz

답안 #848281

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
848281 2023-09-12T01:19:57 Z wakandaaa 최솟값 배열 (IZhO11_hyper) C++17
0 / 100
 399 ms 83404 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 = 1e9;
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 10584 KB Output is correct
3 Correct 4 ms 19032 KB Output is correct
4 Correct 5 ms 19032 KB Output is correct
5 Correct 4 ms 19032 KB Output is correct
6 Correct 14 ms 29784 KB Output is correct
7 Correct 12 ms 29528 KB Output is correct
8 Correct 36 ms 39016 KB Output is correct
9 Correct 52 ms 40528 KB Output is correct
10 Correct 36 ms 38992 KB Output is correct
11 Correct 95 ms 50096 KB Output is correct
12 Correct 210 ms 65144 KB Output is correct
13 Correct 192 ms 64080 KB Output is correct
14 Correct 252 ms 70224 KB Output is correct
15 Incorrect 399 ms 83404 KB Output isn't correct
16 Halted 0 ms 0 KB -