Submission #1111353

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111353		haianhnguyen08102007	Teams (CEOI11_tea)	C++17	100 / 100	469 ms	121328 KiB

tea

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>

#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define foru(i,a,b) for(int i = (a); i <= (b); ++i)
#define ford(i,a,b) for(int i = (a); i >= (b); --i)

template<typename T> bool maximize(T &res, const T &val) { if (res < val) { res = val; return true; } return false; }
template<typename T> bool minimize(T &res, const T &val) { if (val < res) { res = val; return true; } return false; }

using namespace std;

const int N = 1e6 + 5;

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

//    freopen("DIVTEAM.inp", "r", stdin);
//    freopen("DIVTEAM.out", "w", stdout);

    int n; cin>>n;
    vector <int> a[n+1]; vector <int> v(n+1);
    for (int i=1; i<=n; i++)
    {
        cin>>v[i];
        a[v[i]].pb(i);
    }
    sort(all(v));
    vector <int> dp(n+1, -N); vector <int> mx(n+1);

    function <int (int)> check = [&](int lim)
    {
        dp.assign(n+1, -N); dp[0] = 0;
        for (int i=1; i<=n; i++)
        {
            if (i>=v[i] && i-mx[i-v[i]]<=lim) dp[i] = dp[mx[i-v[i]]] + 1;
            mx[i] = (dp[mx[i-1]] > dp[i] ? mx[i-1] : i);
        }
        return dp[n];
    };

    int mx1 = check(n), l = 0, r = n;
    while (r - l > 1)
    {
        int m = (l + r) / 2;
        if (check(m) == mx1) r = m;
        else l = m;
    }
    check(r);

    vector<vector <int>>ans;
    int p = n;
    while (p>0)
    {
        ans.pb(vector<int>());
        int t = mx[p-v[p]];
        while (p>t)
        {
            ans.back().pb(a[v[p]].back());
            a[v[p]].pop_back();
            p--;
        }
    }

    cout<<mx1<<'\n';
    for (auto &i : ans)
    {
        cout<<i.size()<<' ';
        for (int j : i) cout<<j<<' ';

        cout<<'\n';
    }

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10