oj.uz

Submission #1111353

# Submission time Handle Problem Language Result Execution time Memory
1111353 2024-11-12T07:27:14 Z haianhnguyen08102007 Teams (CEOI11_tea) C++17
100 / 100
 469 ms 121328 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 1 ms 336 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 848 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 696 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 848 KB Output is correct
2 Correct 2 ms 848 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 6244 KB Output is correct
2 Correct 21 ms 6480 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6988 KB Output is correct
2 Correct 19 ms 6224 KB Output is correct
3 Correct 25 ms 6988 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 56392 KB Output is correct
2 Correct 233 ms 56364 KB Output is correct
3 Correct 239 ms 55892 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 73632 KB Output is correct
2 Correct 439 ms 121328 KB Output is correct
3 Correct 331 ms 75764 KB Output is correct
4 Correct 398 ms 67016 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 73548 KB Output is correct
2 Correct 254 ms 70748 KB Output is correct
3 Correct 333 ms 73472 KB Output is correct
4 Correct 469 ms 77416 KB Output is correct