글 읽기 - 번역이 잘못 된 것 같습니다.

lim551 4년 전 0

입력 설명 마지막 줄에

"클러스터의 떨어짐을 구할때 각 열의 가장 바닥만 고려해도 해결할 수 있는 입력만 주어진다."

라는 말이 있는데, 원문에는 그런 언급이 없습니다.

실제로 각 열의 가장 바닥만 고려해서 구현하면 WA가 뜨고 클러스터의 모든 청크를 고려해서 구현하면 AC가 뜹니다.

아래는 WA가 뜬 코드입니다.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<class key, class value, class cmp = less<key>>
using treemap = tree<key, value, less<int>, rb_tree_tag, tree_order_statistics_node_update>; // key, val, comp, implements, 노드 불변 규칙
template<class key, class cmp = less<key>>
using treeset = tree<key, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;

#ifdef LOCAL_BOOKNU
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

// ........................macro.......................... //
#define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
#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 pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
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); }
const i64 MOD = 1e9+7;
inline i64 POW(i64 a, i64 n) {
	assert(0 <= n);
	i64 ret;
	for(ret = 1; n; a = a*a%MOD, n /= 2) { if(n%2) ret = ret*a%MOD; }
	return ret;
}
template <class T> ostream& operator<<(ostream& os, vector<T> v) {
	os << "[";
	int cnt = 0;
	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
	return os << "]";
}
template <class T> ostream& operator<<(ostream& os, set<T> v) {
	os << "[";
	int cnt = 0;
	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
	return os << "]";
}
template <class L, class R> ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
// ....................................................... //

const int MAXN = 1e2+10;
const int dy[4] = { 0, 0, -1, 1 }, dx[4] = { -1, 1, 0, 0 };
int n, m, q, my, vis[MAXN][MAXN];
vii lis;
map<int, int> mp;
string g[MAXN];
void input() {
	cin >> n >> m;
	RFOR(i, n, 1) cin >> g[i];
	g[0] = string(m, 'x');
	cin >> q;
}

void remv(int h, int dir) {
	if(dir) {
		FOR(x, 0, m) if(g[h][x] == 'x') {
			g[h][x] = '.';
			return;
		}
	} else {
		RFOR(x, m-1, 0) if(g[h][x] == 'x') {
			g[h][x] = '.';
			return;
		}
	}
}

void f(int y, int x) {
	vis[y][x] = 1;
	lis.pb({y,x});
	my = min(my, y);
	if(mp.find(x) == mp.end()) mp[x] = y;
	else mp[x] = min(y, mp[x]);
	FOR(dir, 0, 4) {
		int ny = y+dy[dir], nx = x+dx[dir];
		if(1 <= ny && ny <= n && 0 <= nx && nx < m && g[ny][nx] == 'x' && !vis[ny][nx]) {
			f(ny, nx);
		}
	}
}

void norm() {
	int mdy = MAXN*2;
	for(auto[x, y] : mp) {
		RFOR(py, y-1, 0) {
			if(g[py][x] == 'x') {
				mdy = min(mdy, y-py-1);
				break;
			}
		}
	}
	for(auto [y, x] : lis) g[y][x] = '.';
	for(auto [y, x] : lis) g[y-mdy][x] = 'x';
}

int solve() {
	int dir = 0;
	while(q--) {
		int h; cin >> h;
		remv(h, dir ^= 1);
		bool ok = false;
		memset(vis, 0, sizeof(vis));
		FOR(y, 1, n+1) {
			FOR(x, 0, m) {
				if(g[y][x] == '.' || vis[y][x]) continue;
				my = MAXN*2;
				lis.clear();
				mp.clear();
				f(y, x);
				if(my != 1) {
					norm();
					ok = true;
					break;
				}
			}
			if(ok) break;
		}
	}
	RFOR(y, n, 1) cout << g[y] << ENDL;
	return 0;
}

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

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

startlink 4년 전 0

그 조건은 https://www.acmicpc.net/problem/2933 문제에 있습니다.

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

문제

문제

출처

ICPC

번역이 잘못 된 것 같습니다.

lim551 4년 전 0

startlink 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말