497 - Strategic Defense Initiative

 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

string inp;

void solve()
{
    vector<int> nums;
    while (getline(cin, inp) && inp != "") {
        // cout << inp << endl;
        nums.push_back(stoi(inp));
    }

    if (nums.size() == 0) {
        cout << "Max hits: " << 0 << endl;
        return;
    }

    // lis
    int n = nums.size();
    vector<ii> lis(n, ii(INT_MAX, -1));
    vector<int> path(n, -1);
    for (int i = 0; i < n; i++) {
        auto it = lower_bound(lis.begin(), lis.end(), ii(nums[i], -1));
        *it = ii(nums[i], i);
        if (it != lis.begin())
            path[i] = next(it, -1)->second;
    }

    int len = 0;
    for (int i = 0; i < n; i++) {
        if (lis[i].first != INT_MAX)
            len = i;
        else
            break;
    }

    len++;
    cout << "Max hits: " << len << endl;
    vector<int> seq;
    int who = lis[len - 1].second;
    while (who != -1) {
        seq.push_back(nums[who]);
        who = path[who];
    }
    reverse(seq.begin(), seq.end());

    for (int i = 0; i < len; i++) {
        // cout << "index " << i << " " << len << endl;
        cout << seq[i] << endl;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    getline(cin, inp);
    int ncase = stoi(inp);
    getline(cin, inp);
    while (ncase--) {
        solve();

        if (ncase)
            cout << endl;
    }
    return 0;
}