Submission #1146942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146942		Matjaz	Teams (CEOI11_tea)	C++17	0 / 100	398 ms	327680 KiB

tea

#include<iostream>
#include<vector>
#include<algorithm>
#include <deque>

using namespace std;


int main(){

	int N;
	cin >> N;
    vector<pair<int,int> > a(N);

    for (int i=0;i<N;i++) {
    	cin >> a[i].first;
    	a[i].second = i + 1;
    }

    sort(a.begin(), a.end());

	vector<int> teams(N, 0);
	vector<int> minmaxteam(N, N);
	vector<int> next(N, -1);

	vector<int> cumulmax_teams(N, 0);

	for (int i=0;i<N;i++){
		if (a[i].first > i + 1) teams[i] = 0; else {
			if (i - a[i].first < 0) teams[i] = 1; else teams[i] = 1 + cumulmax_teams[i - a[i].first];
		}
		if (i == 0) cumulmax_teams[i] = teams[i]; else cumulmax_teams[i] = max(teams[i],cumulmax_teams[i - 1]);
	}

	vector<deque<int> > d(N + 1);


    for (int i=0;i<N;i++){
    	minmaxteam[i] = i + 1; 

    	if (teams[i] > 1) {
    		deque<int>::iterator e = upper_bound(d[teams[i] - 1].begin(), d[teams[i] - 1].end(), i-a[i].first);

    		for (deque<int>::iterator it=d[teams[i] - 1].begin(); it != e; it++){
    			int j = *it;
    			if (minmaxteam[i] > max(i-j, minmaxteam[j])){
    				minmaxteam[i] = min(minmaxteam[i], max(i-j, minmaxteam[j]));
    				next[i] = j;
    			}
    		}
    	}

    	while (minmaxteam[d[teams[i]].back()] >= minmaxteam[i]) d[teams[i]].pop_back();

    	d[teams[i]].push_back(i);
    }

    cout << teams[N - 1] << endl;
    int cur = N - 1;
    while (cur > -1){
    	cout << cur - next[cur];
    	for (int i=next[cur]+1; i<=cur;i++) cout << " " << a[i].second;
    	cout << endl;
        cur = next[cur];
    }

	return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10