# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1146805 | Matjaz | Teams (CEOI11_tea) | C11 | 0 ms | 0 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);
for (int i=0;i<N;i++){
if (a[i].first > i + 1) teams[i] = 0; else {
teams[i] = 1;
for (int j=0;j<=i - a[i].first;j++) teams[i] = max(teams[i], teams[j] + 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;
}