크립톤 행성의 경기장

시간 제한10초메모리 제한512 MB

요약
각 구간 i가 점 i를 포함하는 n개의 구간이 주어질 때, 두 도시를 함께 수용하는 구간의 존재 여부에 따라 배치를 Great, Acceptable, Bad로 분류한다.
난이도

어려움10점 중 8점

유형
구간, 그리디, 정렬, 배열
정답자
아직 제출이 없습니다

문제

크립톤 행성에는 도시가 nn개 있다. 도시는 서쪽에서 동쪽으로 뻗은 직선 위 서로 다른 지점에 놓여 있고, 서쪽부터 차례로 0,1,2,…,n−10, 1, 2, \dots, n-1번이다. 도시마다 팀이 하나, 경기장이 하나 있다.

경기장 ii에는 정수 aia_i와 bib_i가 붙어 있다. 도시 xx의 팀은 ai≤x≤bia_i \le x \le b_i일 때만 경기장 ii에서 경기한다. 모든 팀이 자기 도시의 경기장에서 경기하도록 ai≤i≤bia_i \le i \le b_i가 보장된다.

다음 시즌 일정을 짜기 전에 도시와 경기장의 배치를 세 등급 가운데 하나로 판정한다.

  • 모든 도시 쌍 c1c_1, c2c_2에 대해 min⁡(c1,c2)≤i≤max⁡(c1,c2)\min(c_1, c_2) \le i \le \max(c_1, c_2)인 경기장 ii 중에 두 도시의 팀을 모두 받는 경기장이 있으면 배치는 Great이다.
  • Great은 아니지만 모든 도시 쌍 c1c_1, c2c_2에 대해 두 팀을 모두 받는 경기장이 어딘가에 있으면 배치는 Acceptable이다.
  • 두 팀을 모두 받는 경기장이 하나도 없는 도시 쌍이 있으면 배치는 Bad이다.

입력

입력은 테스트 케이스 여러 개로 이루어지고 파일 끝에서 끝난다.

각 테스트 케이스의 첫 줄에는 도시의 수 nn이 주어진다 (2≤n≤200 0002 \le n \le 200\,000). 이어지는 nn개의 줄에는 경기장 00번부터 n−1n-1번까지의 구간이 순서대로 주어진다. 각 줄은 정확히 여섯 글자이고, 앞의 세 글자가 aia_i, 뒤의 세 글자가 bib_i다. 세 글자는 각각 0-9A-Za-z 순서를 자릿값 00부터 6161까지로 삼는 62진수 세 자리다. 예를 들어 도시 00, 11, 99, 1010, 3535, 3636, 6161, 6262, 199 999199\,999는 각각 000, 001, 009, 00A, 00Z, 00a, 00z, 010, q1n으로 적는다. 항상 0≤ai≤i≤bi≤n−10 \le a_i \le i \le b_i \le n-1이다.

테스트 케이스는 1 0001\,000개를 넘지 않고, 모든 테스트 케이스의 경기장 수를 합해도 2 000 0002\,000\,000개를 넘지 않는다.

출력

각 테스트 케이스마다 Great, Acceptable, Bad 가운데 하나를 한 줄에 출력한다.

예제2

  1. 예제 1

    입력
    4
    000001
    000003
    002002
    002003
    4
    000000
    001001
    002002
    003003
    4
    000001
    000003
    002002
    003003
    
    예상 출력
    Great
    Bad
    Acceptable
    
  2. 예제 2

    입력
    2
    000001
    000001
    2
    000001
    001001
    2
    000000
    000001
    2
    000000
    001001
    
    예상 출력
    Great
    Great
    Great
    Bad