Submission #1108629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108629		Szil	Volontiranje (COCI21_volontiranje)	C++17	50 / 110	1048 ms	39676 KiB

Main

#include <bits/stdc++.h>

using ll = long long;
using namespace std;

const int MAXN = 1'000'001;

int a[MAXN];

void solve() {
    int n; cin >> n;
    vector<int> lis;
    vector<int> v;
    vector<bool> ok(n+1, true);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        auto it = upper_bound(lis.begin(), lis.end(), a[i]);
        v.emplace_back(it-lis.begin());
        if (it == lis.end()) {
            lis.emplace_back(a[i]);
        } else {
            *it = a[i];
        }
    }
    int ans = lis.size();
    vector<vector<int>> ans2;
    while (true) {
        vector<pair<int, int>> l;
        l.emplace_back(0, 0);
        vector<int> last(n+1);
        for (int i = 1; i <= n; i++) {
            if (!ok[i]) continue;
            auto it = upper_bound(l.begin(), l.end(), make_pair(a[i], 0));
            last[i] = prev(it)->second;
            if (it == l.end()) {
                l.emplace_back(a[i], i);
            } else {
                *it = {a[i], i};
            }
        }
        int u = l.back().second;
        vector<int> p;
        while (u) {
            p.emplace_back(u);
            u = last[u];
        }
        if (p.size() != ans) break;
        reverse(p.begin(), p.end());
        ans2.emplace_back(p);
        for (int i : p) {
            ok[i] = 0;
        }
    }
    cout << ans2.size() << " " << ans << "\n";
    for (auto &x : ans2) {
        for (int i : x) cout << i << " ";
        cout << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:47:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |         if (p.size() != ans) break;
      |             ~~~~~~~~~^~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 0 / 60