13. Uva-12356 Army buddies

문제

<그림1: 문제설명>

이거 bitset같은 S-length의 bit배열로 살아있는 군인 표시 하려고 하면 시간제한에 걸림(2중 for문 써야하기 때문)

따라서 공간을 낭비하더라도 다음과 같이 풀어야함

 

#include<iostream>
using namespace std;
int lefts[100001];
int rights[100001];	//because of restriction of stack size, define it to global.
int main()
{
	int S, B, L, R;
	while (cin >> S >> B) {
		if (S == 0 && B == 0) {//terminal case
			break;
		}
		for (int i = 1; i <= S; i++) {
			lefts[i] = i - 1; 
			rights[i] = i + 1;
		}
		lefts[1] = -1; //-1 means NAN
		rights[S] = -1;
		for (int i = 0; i < B; i++) { //for all loss reports
			cin >> L >> R;
			lefts[rights[R]] = lefts[L];
			if (lefts[L] == -1) cout << "* ";
			else cout << lefts[L] << " ";
			
			rights[lefts[L]] = rights[R];
			if (rights[R] == -1) cout << "*"<<endl;
			else cout << rights[R] << endl;
		}
		cout << "-" << endl;
	}
	return 0;
}

어떤 놈의 왼쪽, 오른쪽에 몇번째 soldier가 오는지 표시하는 배열을 사용했음. L부터 R까지 지우면, L의 왼쪽에 있었던 놈은 R의 오른쪽에 있었던 놈의 왼쪽에 오게 되니까 그걸 표현한게 lefts[rights[R]] = lefts[L]; 마찬가지로 R의 오른쪽에 있었던 놈은 L의 왼쪽에 있었던 놈의 오른쪽에 오게 되니까 그걸 표현한게 rights[lefts[L]] = rights[R];

근데 옆에 암것도 없는 경우를 표현해야 하니까 그걸 -1로 lefts[1]과 rights[S ]의 양 마지막 원소에 넣어놨음. 그래서 만약 대입하는 lefts[L], rights[R]가 -1이면 *을 출력하게 하면 됨.