Codeforces Round #767 (Div. 1) A. Meximum Array

Solution

pos에는 각 num의 idx를 저장해 놓는다. 0 ... n까지 돌면서 이진 탐색을 st 기준으로 이상인 idx가 없으면 해당 값이 mem이 된다. ed값은 각 num의 이진 탐색 결과로 max 갱신을 해주고 그 다음 ed의 위치부터 탐색하도록 st를 갱신하면 된다.

#include <iostream>
#include <vector>
#include <map>
#include <set>

using namespace std;
int main() {
    int rep, n, num;
    cin>>rep;
    while(rep--) {
        cin>>n;
        vector<set<int>> pos(n + 1, set<int>());
        vector<int> res;
        int st = 0, ed, mem;
        for(int i = 0; i < n; i++) {
            cin>>num;
            pos[num].insert(i);
        }

        while(st < n) {
            mem = 0;
            ed = st;
            for(; mem < n; mem++) {
                auto it = pos[mem].lower_bound(st);
                if(it == pos[mem].end()) break;
                ed = max(ed, *it);
            }
            res.push_back(mem);
            st = ed + 1;
        }

        cout<<res.size()<<endl;
        for(auto& ans : res)
            cout<<ans<<" ";
        cout<<endl;

    }
    return 0;
}