oj.uz

Submission #902819

# Submission time Handle Problem Language Result Execution time Memory
902819 2024-01-11T03:19:58 Z Darren0724 Teams (CEOI11_tea) C++17
100 / 100
 1510 ms 106148 KB 
#include <bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define all(x) x.begin(), x.end()
const int N=200005;
 
 
int32_t main() {
    LCBorz;
    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]].push_back(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);
    int l=0,r=n;
    while(r-l>1){
        int m=(l+r)>>1;
        if(check(m)==mx1){
            r=m;
        }
        else{
            l=m;
        }
    }
    check(r);
    vector<vector<int>> ans;
    int p=n;
    while(p>0){
        ans.push_back(vector<int>());
        int t=mx[p-v[p]];
        while(p>t){
            ans.back().push_back(a[v[p]].back());
            a[v[p]].pop_back();
            p--;
        }
    }
    cout<<mx1<<endl;
    for(auto &i:ans){
        cout<<i.size()<<' ';
        for(int j:i){
            cout<<j<<' ';
        }
        cout<<endl;
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 352 KB Output is correct
5 Correct 0 ms 360 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4444 KB Output is correct
2 Correct 30 ms 4696 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 4956 KB Output is correct
2 Correct 24 ms 4700 KB Output is correct
3 Correct 25 ms 5416 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 40056 KB Output is correct
2 Correct 236 ms 42476 KB Output is correct
3 Correct 235 ms 44120 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 52496 KB Output is correct
2 Correct 1510 ms 106148 KB Output is correct
3 Correct 297 ms 56624 KB Output is correct
4 Correct 348 ms 52396 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 52488 KB Output is correct
2 Correct 352 ms 58304 KB Output is correct
3 Correct 322 ms 56152 KB Output is correct
4 Correct 443 ms 60148 KB Output is correct