求助,最后一个数据不过
查看原帖
求助,最后一个数据不过
268809
cheetahes_楼主2023/12/20 15:34
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long
#define ull unsigned long long
const int N=1e5+5;
const int P=1e9+7;
struct node{
    int k;
    int lis[1000];
    int lis_k[1000];
};
int p[N],rk[N];
node dp[N];
int n,m,ch,u,v,op;

int x,y,z,q,k,t;
string s;
ll ans,res,temp;
int binary_search(int l,int r,int val){
    // while(l<r){
    //     int mid=(l+r)/2;
    //     if(dp[mid].lis[dp[mid].k]<val) l=mid+1;
    //     else r=mid;
    // }
    // return r;
    for(int i=r;i>=l;i--){
        if(dp[i].lis[dp[i].k]<val) return i+1;
    }
    return l;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++) {
        cin>>p[i];
        rk[p[i]]=i;
    }
    int len=0,pos=0;
    for(int i=1;i<=n;i++){
        pos=binary_search(1,len,p[i]);
        len=max(len,pos);
        dp[pos].k++;
        dp[pos].lis[dp[pos].k]=p[i];
        dp[pos].lis_k[dp[pos].k]=dp[pos-1].k;
        if(len==k){
            int pre_k=dp[len].k;
            for(int j=len;j>=1;j--){
                p[j]=dp[j].lis[pre_k];
                pre_k=dp[j].lis_k[pre_k];
            }
            cout<<len<<endl;
            for(int j=1;j<=len;j++) cout<<rk[p[j]]<<" "; cout<<endl;
            return 0;
        }
    }
    cout<<-1<<endl;
}
2023/12/20 15:34
加载中...