글 읽기 - 반례 찾습니다.

milkclouds 3년 전 0

왜 안될까요..ㅠㅠ

반례를 모르겠습니다.

#include <bits/stdc++.h>
#define rep(a,b,c) for(ll a = b; a < c; a++)
#define rep2(a,b,c) for(ll a = c - 1; a >=b; a--)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define x first
#define y second
using namespace std;
using ll = long long;
using tl = tuple<ll, ll, ll>;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
const int MAX = 1e3 + 5;

int N, a[MAX], vis[MAX], flag;
pi P[MAX];
string ans[MAX];
vector<pi> adj[MAX];

void make_edge(int u, int v, int f) {
	adj[u].pb({ v, f });
	adj[v].pb({ u, f });
}

void dfs(int u, int f) {
	if (vis[u]) {
		if (vis[u] ^ f) flag = 1;
		return;
	}
	vis[u] = f;
	for (auto p : adj[u]) {
		dfs(p.x, p.y * f);
	}
}

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cin >> N;
	rep(i, 0, N) P[i + 1].x = -1;
	rep(i, 0, N * 2) {
		cin >> a[i];
		if (~P[a[i]].x) P[a[i]].y = i;
		else P[a[i]].x = i;
	}
	rep(i, 1, N + 1) rep(j, i + 1, N + 1) {
		if (P[i].y < P[j].x || P[j].y < P[i].x) continue;
		if (P[i].x < P[j].x && P[j].y < P[i].y) {
			make_edge(P[j].x, P[j].y, 1);
			continue;
		}
		swap(i, j);
		if (P[i].x < P[j].x && P[j].y < P[i].y) {
			make_edge(P[j].x, P[j].y, 1);
			swap(i, j);
			continue;
		}
		swap(i, j);
		if (P[i].x < P[j].x) { make_edge(P[j].x, P[i].y, -1); continue; }
		swap(i, j);
		make_edge(P[j].x, P[i].y, -1);
		swap(i, j);
	}
	rep(i, 0, N * 2) if (!vis[i]) dfs(i, 1);
	if (flag) { cout << "NO\n"; return 0; }
	cout << "YES\n";
	rep(k, 0, N * 2) {
		int i = a[k];
		if (P[i].y != k) continue;
		string s = ~vis[P[i].x] ? " U " : " D ";
		string s2 = ~vis[P[i].x] ? " D " : " U ";
		int l = P[i].y + 1;
		if (vis[P[i].x] ^ vis[P[i].y]) {
			ans[i] = to_string(5) + s + to_string(l) + " L " + to_string(l * 2) + s2 + to_string(l * 2) + " R " + to_string(P[i].y - (P[i].x - l * 2)) +  s + to_string(l) + "\n";
		}
		else {
			ans[i] = to_string(3) + s + to_string(l) + " R " + to_string(P[i].y - P[i].x) + s2 + to_string(l) + "\n";
		}
	}
	rep(i, 0, N) cout << ans[i + 1];
}

milkclouds 3년 전 1

1. 위쪽 선분이 2l이 아니라, 아래쪽 선분이 2l이어야 합니다.

(반대 방향인 패드 사이로 움직이는 도형의 왼쪽 선분이 -l에 있어야 합니다.)

2. 배열 크기 2배로 잡아야 합니다.

해결했습니다.

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

문제

문제

출처

ICPC

반례 찾습니다.

milkclouds 3년 전 0

milkclouds 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말