Submission #510088

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
510088	2022-01-14T17:20:39 Z	blue	Teams (CEOI11_tea)	C++17	0 / 100	328 ms	54840 KB

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using vi = vector<int>;
using pii = pair<int, int>;
using vvi = vector<vi>;
#define sz(x) int(x.size())

const int INF = 100'000'000;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    pii a[1+n];
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a+1, a+n+1);

    int t;

    vi dp(1+n);

    vi occ[1+n];

    vi bit(1+n+1, -INF);
    // bit[0 +1] = 0;
    for(int j = 0 +1; j <= n +1; j += j&-j) bit[j] = 0;

    occ[0].push_back(0);

    for(int i = 1; i <= n; i++)
    {
        t = -INF;
        if(a[i].first > i)
        {
            ;
        }
        else
        {
            for(int j = i - a[i].first +1; j >= 0 +1; j -= j&-j)
                t = max(t, bit[j]+1);

            // cerr << i << " -> " << i - a[i].first << '\n';

            for(int j = i +1; j <= n +1; j += j&-j)
                bit[j] = max(bit[j], t);
        }

        dp[i] = t;
        if(t != -INF) occ[dp[i]].push_back(i);

        // cerr << i << " : " << t << '\n';
    }

    vvi teams;
    int I = n;
    // cerr << "done\n";

    while(t)
    {
        // cerr << "I = " << I << '\n';
        teams.push_back(vi(0));
        // cerr << "A\n";

        while(sz(occ[t-1]) >= 2 && occ[t-1].back() > I - a[I].first)
            occ[t-1].pop_back();

        // cerr << "B\n";
        // cerr << t-1 << " : " << sz(occ[t-1]) << '\n';

        for(int j = occ[t-1].back()+1; j <= I; j++)
            teams.back().push_back(a[j].second);

        // cerr << "C\n";

        I = occ[t-1].back();

        // cerr << "D\n";

        t--;
    }


    cout << sz(teams) << '\n';
    for(int y = 0; y < sz(teams); y++)
    {
        cout << sz(teams[y]) << ' ';
        for(int z: teams[y]) cout << z << ' ';
        cout << '\n';
    }
}

Compilation message

tea.cpp: In function 'int main()':
tea.cpp:30:9: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
   30 |     int t;
      |         ^

Subtask #1
0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	204 KB	Output is correct
2	Correct	204 KB	Output is correct
3	Incorrect	204 KB	Output isn't correct
4	Halted	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	204 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	204 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	588 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	588 KB	Output is correct
2	Incorrect	2 ms	588 KB	Output isn't correct

Subtask #6
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	25 ms	4636 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	29 ms	5124 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	272 ms	41604 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	328 ms	54504 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	312 ms	54840 KB	Output isn't correct
2	Halted	0 ms	0 KB	-