oj.uz

Submission #497320

# Submission time Handle Problem Language Result Execution time Memory
497320 2021-12-23T03:02:40 Z SirCovidThe19th Teams (CEOI11_tea) C++17
70 / 100
 2500 ms 66736 KB 
#include <bits/stdc++.h>
using namespace std; 

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    int n; cin >> n; pair<int, int> A[n + 1]; 
    for (int i = 1; i <= n; i++) cin >> A[i].first, A[i].second = i;
    sort(A + 1, A + n + 1);

    auto maxTeams = [&](int mxsz, bool get){
        int dp[n + 1] = {}, sz[n + 1] = {}, l = 0, r = 0; 
        set<pair<int, int>> vals; vals.insert({0, 0});

        for (int i = 1; i <= n; i++){
            int newL = max(i - mxsz, 0), newR = i - A[i].first;
            if (newR < newL){ dp[i] = -1e9; continue; }

            while (r < newR) r++, vals.insert({dp[r], r});
            while (r > newR) vals.erase({dp[r], r}), r--;
            while (l < newL) vals.erase({dp[l], l}), l++;

            dp[i] = vals.rbegin()->first + 1;
            sz[i] = i - vals.rbegin()->second;
        }
        if (get){
            cout<<dp[n]<<"\n";
            for (int pos = n; pos; pos -= sz[pos]){
                cout<<sz[pos]<<" ";
                for (int i = pos; i > pos - sz[pos]; i--) cout<<A[i].second<<" ";
                cout<<"\n";
            }
        }
        return dp[n];
    };
    int L = 1, H = n, mx = maxTeams(1e9, 0);
    while (L < H){
        int M = (L + H) / 2;
        (maxTeams(M, 0) == mx) ? H = M : L = M + 1;
    }
    maxTeams(H, 1);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 316 KB Output is correct
4 Correct 0 ms 312 KB Output is correct
5 Correct 1 ms 208 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 584 KB Output is correct
2 Correct 8 ms 592 KB Output is correct
3 Correct 11 ms 648 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 460 KB Output is correct
2 Correct 8 ms 592 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 5248 KB Output is correct
2 Correct 219 ms 5948 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 6356 KB Output is correct
2 Correct 213 ms 5592 KB Output is correct
3 Correct 229 ms 6360 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2517 ms 51728 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2561 ms 64460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1652 ms 53284 KB Output is correct
2 Correct 308 ms 30640 KB Output is correct
3 Execution timed out 2511 ms 66736 KB Time limit exceeded
4 Halted 0 ms 0 KB -