Submission #1185531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185531		Esgeer	Volontiranje (COCI21_volontiranje)	C++20	10 / 110	1 ms	328 KiB

Main

#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize("O3")
#define vi vector<int>
#define vb vector<bool>
#define F(i, s, e) for(int i = s; i < e; i++)
#define sp <<' '<<
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define vvi vector<vi>
#define vpi vector<pii>
#define vvpi vector<vpi>
#define endl '\n'
 
const int mod = 1e9 + 7;
 
using namespace std;

const int inf = 1e15;
const int K = 12;
const int N = 1ll << K;

bitset<K> have;

void solve() {
    int n;
    cin >> n;
    vi a(n), dp(n);
    F(i, 0, n) cin >> a[i];

    vi lis;
    F(i, 0, n) {
        auto ptr = lower_bound(lis.begin(), lis.end(), a[i]);

        if(ptr == lis.end()) {
            lis.push_back(a[i]);
            dp[i] = lis.size();
        } else {
            *ptr = a[i];
            dp[i] = ptr - lis.begin() + 1;
        }
    }

    vvi stacks(n+1);
    F(i, 0, n) {
        stacks[dp[i]].pb(i);
    }

    int l = lis.size();
    vvi ans;
    while(!stacks[l].empty()) {
        int me = stacks[l].back();
        vi curs;
        int curl = dp[me];
        stacks[l].pop_back();
        bool flag = 1;
        curs.pb(me);
        while(dp[me] > 1) {
            while(stacks[curl-1].size() && stacks[curl-1].back() >= me) stacks[curl-1].pop_back();
            if(stacks[curl-1].size() && a[stacks[curl-1].back()] < a[me]) {
                me = stacks[curl-1].back();
                stacks[curl-1].pop_back();
                curl = dp[me];
                curs.pb(me);
            } else {
                flag = 0;
                break;
            }
        }
        if(flag) ans.pb(curs);
    }
    cout << ans.size() sp l << endl;
    for(auto &anss : ans) {
        for(int i = anss.size() - 1; i >= 0; i--) cout << anss[i]+1 << " ";
        cout << endl;
    }
}
 
int32_t main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    #ifdef Local
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif
    int t = 1;
    //cin >> t;
    while(t--) solve();
}

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