#include <bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define all(x) x.begin(), x.end()
const int N=200005;
#define endl '\n'
int32_t main() {
LCBorz;
int n;cin>>n;
vector<int> a[n+1];
vector<int> v(n+1);
for(int i=1;i<=n;i++){
cin>>v[i];
a[v[i]].push_back(i);
}
sort(all(v));
vector<int> dp(n+1,-N);
vector<int> mx(n+1);
function<int(int)> check=[&](int lim){
dp.assign(n+1,-N);
dp[0]=0;
for(int i=1;i<=n;i++){
if(i>=v[i]&&i-mx[i-v[i]]<=lim)dp[i]=dp[mx[i-v[i]]]+1;
mx[i]=(dp[mx[i-1]]>dp[i]?mx[i-1]:i);
}
return dp[n];
};
int mx1=check(n);
int l=0,r=n;
while(r-l>1){
int m=(l+r)>>1;
if(check(m)==mx1){
r=m;
}
else{
l=m;
}
}
check(r);
vector<vector<int>> ans;
int p=n;
while(p>0){
ans.push_back(vector<int>());
int t=mx[p-v[p]];
while(p>t){
ans.back().push_back(a[v[p]].back());
a[v[p]].pop_back();
p--;
}
}
cout<<mx1<<endl;
for(auto &i:ans){
cout<<i.size()<<' ';
for(int j:i){
cout<<j<<' ';
}
cout<<endl;
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
600 KB |
Output is correct |
2 |
Correct |
2 ms |
600 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
604 KB |
Output is correct |
2 |
Correct |
2 ms |
676 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
4576 KB |
Output is correct |
2 |
Correct |
20 ms |
4712 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
28 ms |
4968 KB |
Output is correct |
2 |
Correct |
19 ms |
4456 KB |
Output is correct |
3 |
Correct |
24 ms |
4968 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
225 ms |
40168 KB |
Output is correct |
2 |
Correct |
214 ms |
40428 KB |
Output is correct |
3 |
Correct |
231 ms |
39508 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
338 ms |
52708 KB |
Output is correct |
2 |
Correct |
379 ms |
104624 KB |
Output is correct |
3 |
Correct |
276 ms |
53748 KB |
Output is correct |
4 |
Correct |
312 ms |
47400 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
298 ms |
52568 KB |
Output is correct |
2 |
Correct |
277 ms |
50352 KB |
Output is correct |
3 |
Correct |
279 ms |
52332 KB |
Output is correct |
4 |
Correct |
376 ms |
54592 KB |
Output is correct |