Submission #1146809

#TimeUsernameProblemLanguageResultExecution timeMemory
1146809MatjazTeams (CEOI11_tea)C++17
70 / 100
2596 ms23860 KiB
#include<iostream>
#include<vector>
#include<algorithm>

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]);
	}


    for (int i=0;i<N;i++){
    	minmaxteam[i] = i + 1; 
    	for (int j=0;j<=i-a[i].first;j++) if (teams[j] > 0 && teams[j] + 1 == teams[i]){
    		if (minmaxteam[i] > max(i-j, minmaxteam[j])){
    			minmaxteam[i] = min(minmaxteam[i], max(i-j, minmaxteam[j]));
    			next[i] = j;
    		}
    	}
    }

    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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...