Submission #489175

#	Time	Username	Problem	Language	Result	Execution time	Memory
489175		Victor	Volontiranje (COCI21_volontiranje)	C++17	50 / 110	5 ms	616 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

vi answers[1001];
int p[1001];
int cnt = 0;
bitset<1001> taken;

void rec(int i) {
    if (p[i] != -1) rec(p[i]);
    answers[cnt].pb(i);
    taken[i]=1;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int n, arr[1001], lis[1001], len = 0,lis_idx[1001];
    cin >> n;
    rep(i, 0, n) {
        cin >> arr[i];
        int pos = lower_bound(lis, lis + len, arr[i]) - lis;
        lis[pos] = arr[i];
        if (pos == len) ++len;
    }

    rep(j, 0, n) {
        int cur_len = 0, best_end = -1;
        memset(p, -1, sizeof(p));

        rep(i, 0, n) {
            if (taken[i]) continue;

            int pos = lower_bound(lis, lis + cur_len, arr[i]) - lis;
            if (pos) p[i] = lis_idx[pos - 1];
            if (pos + 1 == len) best_end = i;
            lis[pos] = arr[i];
            lis_idx[pos]=i;
            if (pos == cur_len) ++cur_len;
        }

        if (cur_len < len) break;
        rec(best_end);
        ++cnt;
    }

    cout << cnt << ' ' << len << endl;
    rep(i, 0, cnt) {
        rep(j, 0, len) cout << answers[i][j]+1 << ' ';
        cout << endl;
    }
    return 0;
}

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