글 읽기 - 3차원 부분합 시간초과 질문

lim551 5년 전 0

3차원 부분합 + binary search로 O(N + M^3logM)에 풀리는 문제인데, 정해와 같은 알고리즘을 썼는데도 불구하고 시간초과가 나서 질문드립니다.

정해에서는 3차원 부분합을 처리하는 부분에서 ps[x][y][z] = ps[x-1][y][z] + ps[x][y-1][z] + ... + ps[x-1][y-1][z-1]과 같이 직접적으로 코드에 데이터를 넣었고,

저는 코드와 데이터를 분리해서 일관성이 있게 보이려고 위의 여러개의 +들을 dc배열로 표현해 나름 깔끔하게 구현하려고 했습니다. (실제로는 정해보다 더 더러워졌지만;;)

정해는 2500ms만에 AC가 뜨는 반면 제 코드는 첫 테케에서 TLE가 걸립니다. 저렇게 구현하는게 2배 이상의 시간차이나 날 정도로 비효율적일까요?

/************
< 주소 >      : 
*************
< 해결방안 >   :


*************
< 오답노트 >   :

*************/

#ifndef ONLINE_JUDGE
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <bits/stdc++.h>
using namespace std;

// ........................macro.......................... //
// [i, n)
#define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
// [i, n]
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
#define pb push_back
#define emb emplace_back
#define fi first
#define se second
#define ENDL '\n'
#define sz(A) (int)(A).size()
#define ALL(A) A.begin(), A.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
#define next next9876
#define prev prev1234
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<pair<int, int> > vii;
typedef vector<vector<pair<int, int> > > vvii;
typedef pair<int, int> ii;
typedef pair<int, pair<int, int> > iii;
typedef long long i64;
typedef unsigned long long ui64;
// inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
inline i64 GCD(i64 a, i64 b){ i64 n; if(a<b) swap(a, b); while(b!=0) { n = a%b; a = b; b = n; } return a; }
inline i64 LCM(i64 a, i64 b) { if (a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); }
inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d)*2 >= d); }
inline i64 POW(i64 a, i64 n) {
	if (n < 0) return 0;
	i64 ret = 1;
	while (n) { if (n % 2) ret *= a; a = a * a; n /= 2; }
	return ret;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifndef ONLINE_JUDGE
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

// ....................................................... //

class FastIO {
    int fd, bufsz;
    char *buf, *cur, *end;
public:
    FastIO(int _fd = 0, int _bufsz = 1 << 20) : fd(_fd), bufsz(_bufsz) {
        buf = cur = end = new char[bufsz];
    }
    ~FastIO() {
        delete[] buf;
    }
    bool readbuf() {
        cur = buf;
        end = buf + bufsz;
        while (true) {
            size_t res = fread(cur, sizeof(char), end - cur, stdin);
            if (res == 0) break;
            cur += res;
        }
        end = cur;
        cur = buf;
        return buf != end;
    }
    int r() {
        while (true) {
            if (cur == end) readbuf();
            if (isdigit(*cur) || *cur == '-') break;
            ++cur;
        }
        bool sign = true;
        if (*cur == '-') {
            sign = false;
            ++cur;
        }
        int ret = 0;
        while (true) {
            if (cur == end && !readbuf()) break;
            if (!isdigit(*cur)) break;
            ret = ret * 10 + (*cur - '0');
            ++cur;
        }
        return sign ? ret : -ret;
    }
} io;

const int MAXN = 1e5, RANGE = 256;
const vvi dc[3] = {
	{ { -1, 0, 0 }, { 0, -1, 0 }, { 0, 0, -1 } },
	{ { -1, -1, 0 }, { -1, 0, -1 }, {0, -1, -1} },
	{ { -1, -1, -1 } }
};
int n, k, ps[RANGE][RANGE][RANGE], ar[RANGE][RANGE][RANGE];
void input() {
	n = io.r(), k = io.r();
	FOR(i, 0, n) { int x, y, z; x = io.r(), y = io.r(), z = io.r(); ++ps[x][y][z], ++ar[x][y][z]; }
}

int sum(int x1, int y1, int z1, int l) {
	int x[2] = { x1-1, min(RANGE-1, x1 + l) }, y[2] = { y1-1, min(RANGE-1, y1 + l) }, z[2] = { z1-1, min(RANGE-1, z1 + l) };
	int ret = ps[x[1]][y[1]][z[1]];
	FOR(dir, 0, 3) {
		FOR(t, 0, dc[dir].size()) {
			int cx = x[1+dc[dir][t][0]], cy = y[1+dc[dir][t][1]], cz = z[1+dc[dir][t][2]];
			if(cx < 0 || cy < 0 || cz < 0) continue;
			ret += (dir % 2 == 0 ? -ps[cx][cy][cz] : ps[cx][cy][cz]);
		}
	}
	return ret;
}

void init() {
	FOR(x, 0, RANGE) {
		FOR(y, 0, RANGE) {
			FOR(z, 0, RANGE) {
				FOR(dir, 0, 3) {
					FOR(t, 0, dc[dir].size()) {
						int nx = x + dc[dir][t][0], ny = y + dc[dir][t][1], nz = z + dc[dir][t][2];
						if(nx < 0 || ny < 0 || nz < 0) continue;
						ps[x][y][z] += (dir % 2 == 0 ? ps[nx][ny][nz] : -ps[nx][ny][nz]);
					}
				}
			}
		}
	}
}

int solve() {
	init();
	int ax, ay, az, l = -1;
	FOR(x, 0, RANGE) {
		FOR(y, 0, RANGE) {
			FOR(z, 0, RANGE) {
				int lo = -1, hi = RANGE;
				while(lo + 1 < hi) {
					int m = (lo + hi)/2;
					if(sum(x, y, z, m) >= k) hi = m;
					else lo = m;
				}
				if(l == -1 || (l > hi)) {
					l = hi, ax = x, ay = y, az = z;
					debug(ax, ay, az, l, sum(ax, ay, az, l));
				}
			}
		}
	}
	printf("%d\n", l);
	FOR(x, ax, ax + l + 1) {
		FOR(y, ay, ay + l + 1) {
			FOR(z, az, az + l + 1) {
				while(ar[x][y][z] && k) {
					printf("%d %d %d\n", x, y, z);
					--ar[x][y][z], --k;
				}
			}
		}
	}
	return 0;
}

// ................. main .................. //
void execute() {
	input(), solve();
}

int main(void) {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
#endif
	cin.tie(0); ios_base::sync_with_stdio(false);
	execute();
	return 0;
}
// ......................................... //

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

3차원 부분합 시간초과 질문

lim551 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말