QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#728877#880. Film Criticsgambit#TL 1ms5700kbC++171.5kb2024-11-09 16:08:262024-11-09 16:08:27

Judging History

你现在查看的是最新测评结果

  • [2024-11-09 16:08:27]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:5700kb
  • [2024-11-09 16:08:26]
  • 提交

answer

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;

const int NN = 2e5+5;
int N, M, K;
pair<int, int> A[NN];

int tmp[NN];
int calculate(){
    int ans = 0;
    tmp[0] = M;
    for(int i=0;i<N;i++){
        tmp[i]=i*A[i].first;
        // cout<<A[i].first<<' ';
    }
    // cout<<'\n';
    for(int i=0;i<N;i++){
        if(tmp[i]>=M*ans){
            ans++;
        }
    }
    // cout<<'\n'<<'\n';
    return ans;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>N>>M>>K;
    for(int i=0;i<N;i++){
        cin>>A[i].first;
        A[i].second = i+1;
    }
    if(K%M){
        cout<<"impossible";
        return 0;
    }
    K/=M;
    sort(A, A+N);
    int hi = calculate();
    reverse(A, A+N);
    int lo = calculate();
    if(K<lo||hi<K){
        cout<<"impossible";
        return 0;
    }
    if(K==lo){
        for(int i=0;i<N;i++)cout<<A[i].second<<' ';
        return 0;
    }
    reverse(A, A+N);
    if(K==hi){
        for(int i=0;i<N;i++)cout<<A[i].second<<' ';
        return 0;
    }
    reverse(A, A+N);
    while(lo+1<hi){
        int mid = lo+hi>>1;
        // cout<<lo<<' '<<hi<<endl;
        reverse(A, A+mid);
        int rst = calculate();
        if(K==rst){
            for(int i=0;i<N;i++)cout<<A[i].second<<' ';
            return 0;
        }
        if(rst<K){
            lo = rst;
        }
        else hi = rst;
        reverse(A, A+mid);
    }
    cout<<"impossible";
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3624kb

input:

5 10 30
10 5 3 1 3

output:

4 3 5 2 1 

result:

ok OK!

Test #2:

score: 0
Accepted
time: 1ms
memory: 5700kb

input:

5 5 20
5 3 3 3 3

output:

impossible

result:

ok OK!

Test #3:

score: -100
Time Limit Exceeded

input:

5 10 20
6 1 9 3 2

output:


result: