백준8188 Intelligence Test

작성일 | In

문제 링크

  • http://icpc.me/8188

문제 출처

  • POI 2009/2010 Stage 1 5번

사용 알고리즘

  • 이분 탐색

시간복잡도

  • $O(N \log N)$

풀이

선택할 수 있는 가장 앞에 있는 원소를 선택하는 그리디가 성립하는 것을 쉽게 알 수 있습니다.
각 수가 나오는 인덱스를 저장한 뒤, lower_bound를 통해 가능한 가장 작은 인덱스를 선택하면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

int n, m, q, a[1010101];
vector<int> g[1010101];

void qry(){
    cin >> m; int pv = 1;
    for(int i=1; i<=m; i++) cin >> a[i];
    for(int i=1; i<=m; i++){
        int t = a[i];
        auto it = lower_bound(all(g[t]), pv);
        if(it == g[t].end()){ cout << "NIE\n"; return; }
        pv = *it + 1;
    }
    cout << "TAK\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for(int i=1; i<=n; i++){
        int t; cin >> t; g[t].push_back(i);
    }
    cin >> q;
    for(int i=1; i<=q; i++) qry();
}