Submission #392088

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
392088	2021-04-20T13:22:00 Z	nicolaalexandra	Teams (CEOI11_tea)	C++14	70 / 100	2500 ms	177152 KB

#include <bits/stdc++.h>
#define DIM 1000010
#define INF 2000000000
using namespace std;

pair <int,int> dp[DIM],v[DIM];
vector <int> sol[DIM],events[DIM];
vector <pair<int,int> > s;
int t[DIM],p[DIM],rmq[30][DIM];
int n,i,j,k,maxim;

int get_max (int x, int y){
    int nr = p[y-x+1];
    return max (rmq[nr][x],rmq[nr][y-(1<<nr)+1]);
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n;
    for (i=1;i<=n;i++){
        cin>>v[i].first;
        v[i].second = i;
    }

    sort (v+1,v+n+1);
    reverse (v+1,v+n+1);

    for (i=1;i<=n;i++)
        rmq[0][i] = v[i].first;

    for (i=1;(1<<i)<=n;i++)
        for (j=1;j<=n;j++){
            rmq[i][j] = rmq[i-1][j];
            if (j + (1<<(i-1)) <= n && rmq[i-1][j + (1<<(i-1))] > rmq[i][j])
                rmq[i][j] = rmq[i-1][j + (1<<(i-1))];
        }

    for (i=2;i<=n;i++)
        p[i] = p[i/2] + 1;

    /// dp[i] - nr maxim de secv in care pot imparti sirul si care e dimensiunea maxima minima

    for (i=1;i<=n;i++)
        dp[i] = make_pair(-INF,INF);

    /// cand incepe sa aiba influenta un dp?
    for (i=1;i<=n;i++){
        /*int st = i, dr = n, sol = 0;
        while (st <= dr){
            int mid = (st+dr)>>1;
            if (v[i].first <= mid-i+1){
                sol = mid;
                dr = mid-1;
            } else st = mid+1;
        }*/

        events[i + v[i].first - 1].push_back(i-1);
    }

    int maxim = -1;
    for (i=1;i<=n;i++){

        for (auto it : events[i]){
            if (dp[it].first > maxim){
                maxim = dp[it].first;
                s.clear();
                s.push_back(make_pair(dp[it].second,it));
            } else {
                if (dp[it].first == maxim)
                    s.push_back(make_pair(dp[it].second,it));
            }
        }

        if (maxim == -1)
            continue;

        /// calculez dp[i];
        dp[i].first = maxim + 1;
        for (auto it : s){
            if (max(it.first,i-it.second) < dp[i].second){
                dp[i].second = max(it.first,i-it.second);
                t[i] = it.second;
            }
        }
    }

    int x = n;
    while (x > 0){

        ++k;
        for (i=t[x]+1;i<=x;i++)
            sol[k].push_back(v[i].second);

        x = t[x];
    }

    cout<<k<<"\n";
    for (i=1;i<=k;i++){
        cout<<sol[i].size()<<" ";
        for (auto it : sol[i])
            cout<<it<<" ";
        cout<<"\n";
    }


    return 0;
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	47236 KB	Output is correct
2	Correct	30 ms	47308 KB	Output is correct
3	Correct	30 ms	47224 KB	Output is correct
4	Correct	31 ms	47316 KB	Output is correct
5	Correct	30 ms	47340 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	47308 KB	Output is correct
2	Correct	30 ms	47328 KB	Output is correct
3	Correct	31 ms	47296 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	47428 KB	Output is correct
2	Correct	31 ms	47328 KB	Output is correct
3	Correct	30 ms	47368 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	47940 KB	Output is correct
2	Correct	33 ms	47920 KB	Output is correct
3	Correct	34 ms	47948 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	47948 KB	Output is correct
2	Correct	37 ms	47880 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	530 ms	57924 KB	Output is correct
2	Correct	81 ms	58052 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	590 ms	59156 KB	Output is correct
2	Correct	76 ms	57412 KB	Output is correct
3	Correct	544 ms	59216 KB	Output is correct

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2584 ms	146124 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	2538 ms	177152 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 10.0

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

Submission #392088

Compilation message