| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 256 MB | 3023 | 900 | 631 | 30.916% |
문제
국경을 따라 순환 도로를 건설한 국가가 있다. 이 순환 도로에는 N개의 위치에 버스 정류소가 있으며, 버스 정류소에는 0부터 N-1까지 번호가 시계방향 순서로 지정되어 있다. 현재 여러 개의 버스 노선들이 이 순환 도로에서 운행되고 있다. 각 버스 노선은 [a,b]로 표시된다. 이 노선의 버스는 버스 정류소 a부터 b까지를 시계방향으로, b부터 a까지는 반시계방향으로 운행한다. 순환 도로 상의 모든 정류소를 포함하는 버스 노선은 존재하지 않는다.
국가 교통행정부에서 비용 절감을 위해서 버스 노선 중 일부를 취소하려고 한다. 취소되는 노선은 다른 노선에 포함되어 있는 노선이다. 예를 들어, N=10일 때, 5개의 버스 노선이 다음과 같이 있다고 하자.
[0, 4], [2, 6], [5, 0], [7, 9], [9, 4]
위 그림에서 버스 노선 ①은 ⑤에 포함되고, 버스 노선 ④는 ③에 포함된다. 버스 노선 ②, ③, ⑤를 포함하는 노선은 없다. 따라서 취소되는 버스 노선은 ①과 ④이다.
버스 노선에 대한 정보가 주어질 때, 취소되지 않고 계속 운행되는 버스 노선을 모두 출력하는 프로그램을 작성하시오.
입력
첫 번째 줄에는 버스 정류소의 개수 N(3 ≤ N ≤ 1,000,000,000)이 주어지고 두 번째 줄에는 버스 노선의 수 M(2 ≤ M ≤ 500,000)이 주어진다. 각 버스 노선은 1부터 M까지의 번호로 구분된다. 그 다음 M개의 줄에는 1번 노선부터 순서대로 각 버스 노선 [a,b]를 나타내는 두 개의 정수 a와 b가 한 줄에 주어진다, 단, 0 ≤ a, b ≤ N-1이고 a≠b이며 동일한 버스 노선이 두 번 이상 입력으로 주어지는 경우는 없다. 또한 순환 도로 상의 모든 정류소를 포함하는 버스 노선은 존재하지 않는다.
출력
입력으로 주어진 버스 노선들 중에서 다른 노선에 포함되지 않은 노선들의 번호를 번호가 작은 것부터 순서대로 빈칸을 사이에 두고 출력한다.
접근
최근 내가 본 문제들 중에 제일 아름다운 문제였다.
여러가지 알고리즘을 생각해보았는데 뚜렷한 알고리즘이 떠오르지 않았다.
a가 b보다 큰 경우만 없었다면, 쉬운 그리디 문제였는데
이것을 예외처리 할 방법이 크게 떠오르지 않았다.
10분정도 고민해봐도 답이 나오지 않아, 검색을 해봤다.
풀이를 보고 깜짝 놀랬다.
데이터를 이런식으로 전처리 하는 것을 생각도 못했다.
너무 멋진 풀이라는 생각이 들었다.
풀이
a가 b보다 큰 경우를 (a - N, b)와 (a, b + N)으로 나눠서 저장하면 된다.
그리고 평범한 그리디 스위핑을 사용하면 된다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
typedef pair<pair<int, int>, int> PP;
int N, M;
vector<PP> arr;
set<int> ans;
bool comp(PP a, PP b)
{
if (a.first.first == b.first.first)
return a.first.second > b.first.second;
return a.first.first < b.first.first;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
CIN2(N, M);
FUP(i, 1, M)
{
int a, b;
CIN2(a, b);
if (a < b) arr.push_back({ { a, b }, i });
else
{
arr.push_back({ {a - N, b}, i });
arr.push_back({ {a, b + N}, i });
}
}
sort(ALL(arr), comp);
ans.insert(arr[0].second);
int before = arr[0].first.second;
FUP(i, 1, arr.size() - 1)
{
if (before < arr[i].first.second)
{
ans.insert(arr[i].second);
before = arr[i].first.second;
}
}
for (int idx : ans)
{
COUT2(idx, "");
}
return 0;
}