이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |