C++14(g++5.4) 解法, 执行用时: 354ms, 内存消耗: 12132K, 提交时间: 2018-08-07 10:51:13

#include<bits/stdc++.h>
#define ll long long
#define inf 1e18+5
#define M 500005
using namespace std;
ll n,k;
ll tr[M],f[M];
int sz;
int a[M],b[M],ans[M];

int lowbit(int o){
	return o&(-o);
}

void add(int o,ll x){
	while(o>0){
		tr[o]+=x;
		if(tr[o]>=inf)tr[o]=inf;
		o-=lowbit(o);
	}
}

ll query(int o){
	ll sum=0;
	while(o<=sz){
		sum+=tr[o];
		if(sum>=inf){return inf;}
		o+=lowbit(o);
	}
	return sum;
}

int id(int x){
	return lower_bound(b+1,b+sz+1,x)-b;
}

int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		b[i]=a[i];
	}
	sort(b+1,b+n+1);
	sz=unique(b+1,b+n+1)-(b+1);
	
	for(int i=n;i>=1;i--){
		int u=id(a[i]);
		f[i]=query(u+1)+1;
		add(u,f[i]);
	}
	int cnt=0,nw=0;
	for(int i=1;i<=n;i++){
		if(a[i]>nw){
			if(k>f[i]){
				k-=f[i];
			}
			else{
				k--;
				ans[cnt++]=i;
				nw=a[i];
			}
		}
		if(k==0)break;
	}
	if(k||!cnt)printf("-1\n");
	else{
		printf("%d\n",cnt);
		for(int i=0;i<cnt;i++){
			if(i!=0)printf(" ");
			printf("%d",ans[i]);
		}
		printf("\n");
	}
}

C++ 解法, 执行用时: 198ms, 内存消耗: 12152K, 提交时间: 2021-10-05 15:28:38

#include <bits/stdc++.h>

#define fp(i, a, b) for(int i = a, i##_ = (b) + 1; i < i##_; ++i)
using namespace std;
using ll = int64_t;
const ll Inf = 1e18;
const int N = 5e5 + 5;
int n, m, a[N], b[N]; ll k, c[N], f[N];
void mdy(int i, ll w) { for (; i; i -= i & -i) c[i] = min(c[i] + w, Inf); }
ll qry(int i, ll w = 0) { for (; i <= m; i += i & -i) w = min(w + c[i], Inf); return w; }
int main() {
    scanf("%d%lld", &n, &k);
    fp(i, 1, n) scanf("%d", a + i), b[i] = a[i];
    sort(b + 1, b + n + 1), m = unique(b + 1, b + n + 1) - b - 1;
    fp(i, 1, n) a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
    for (int i = n; i; --i) mdy(a[i], f[i] = qry(a[i] + 1) + 1);
    vector<int> g;
    fp(i, 1, n) {
        if (!k || !g.empty() && a[i] <= a[g.back()]) continue;
        if (k > f[i]) k -= f[i];
        else g.push_back(i), --k;
    }
    if (k) return puts("-1"), 0;
    printf("%d\n", g.size());
    for (auto x: g) printf("%d ", x);
    return 0;
}