1부터 N까지의 빵 번호가 주어진다.
세개의 빵을 한번에 뒤집을 수 있는데 가장 오른쪽에 있는 빵이 맨 왼쪽, 나머지는 오른쪽으로 한칸씩 밀려진다.
빵 순서를 사장이 원하는 순서로 바꿀 수 있는지 판단하는 문제다.
정답률이 85%정도 되는데 쉬운문제는 아니다.
직접 손으로 경우를 그려보니 사장이 원하는 순서의 첫번째 숫자부터 맞추면서 판단하면 해결이 가능해보였다.
두 가지 경우로 나뉘었다.
상근이의 6번빵은 5번째 index에 위치하는데 위와같이 6번빵을 당길 수 있다.
이때 사장과 상근이의 빵의 위치의 차이가 홀수인 경우에는 앞에 두 빵을 swap해서 저장해야한다.
짝수인 경우에는 swap할 필요없이 그대로 저장하면 된다.
여기까지는 생각해내는데 금방이였는데 자료구조를 어떻게 구현해야할지 한참걸렸다.
좀 복잡하지만 segment tree를 이용해 구현해냈다.
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N;
int src[100001];
int dst[100001];
int pos[100001];
struct Segment {
vector<int> tree;
int size;
Segment() {}
Segment(int N) :size(N) { tree.resize(4*N, 0); }
int update(int idx, int val, int nl, int nr, int node) {
if (idx < nl || idx > nr) return tree[node];
if (nl == nr) return tree[node] += val;
int mid = (nl + nr) >> 1;
return tree[node] = update(idx, val, nl, mid, node * 2) + update(idx, val, mid + 1, nr, node * 2 + 1);
}
void update(int idx, int val) {
update(idx, val, 0, size - 1, 1);
}
int query(int l, int r, int nl, int nr, int node) {
if (r < nl || l > nr) return 0;
if (l <= nl && nr <= r) return tree[node];
int mid = (nl + nr) >> 1;
return query(l, r, nl, mid, node * 2) + query(l, r, mid + 1, nr, node * 2 + 1);
}
int query(int l, int r) {
return query(l, r, 0, size - 1, 1);
}
int find(int val, int node, int nl, int nr) {
if (nl == nr) return nl;
int mid = (nl + nr) >> 1;
if (tree[node * 2] >= val) return find(val, node*2, nl, mid);
else return find(val - tree[node * 2], node * 2 + 1, mid + 1, nr);
}
int find(int val) {
return find(val, 1, 0, size - 1);
}
};
int main() {
scanf("%d", &N);
Segment seg(N + 1);
for (int n = 0;n < N;n++) scanf("%d", &src[n]), pos[src[n]] = n, seg.update(n, 1);
for (int n = 0;n < N;n++) {
scanf("%d", &dst[n]);
if (n >= N - 2) continue;
int idx = seg.query(0, pos[dst[n]]) - 1;
seg.update(pos[dst[n]], -1);
if ((idx) % 2 == 1) {
int g1 = seg.find(1), g2 = seg.find(2);
swap(pos[src[g1]], pos[src[g2]]);
swap(src[g1], src[g2]);
}
}
if (src[seg.find(1)] == dst[N - 2] && src[seg.find(2)] == dst[N - 1]) printf("Possible\n");
else printf("Impossible\n");
return 0;
}
| cs |
댓글 없음:
댓글 쓰기