QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#728942#880. Film Criticsgambit#WA 1ms5744kbC++172.0kb2024-11-09 16:15:002024-11-09 16:15:00

Judging History

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

  • [2024-11-09 16:15:00]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5744kb
  • [2024-11-09 16:15:00]
  • 提交

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);
    int l = lo, h = hi, t=1000;
    while(t--&&lo+1<hi){
        int mid = lo+hi>>1;
        // cout<<lo<<' '<<hi<<endl;
        reverse(A+mid, A+N);
        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+mid, A+N);
    }
    lo = l, hi = h, t = 1000;
    reverse(A, A+N);
    while(t--&&lo+1<hi){
        int mid = lo+hi>>1;
        reverse(A+mid, A+N);
        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+mid, A+N);
    }

    cout<<"impossible";
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5 10 30
10 5 3 1 3

output:

4 3 5 2 1 

result:

ok OK!

Test #2:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

5 5 20
5 3 3 3 3

output:

impossible

result:

ok OK!

Test #3:

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

input:

5 10 20
6 1 9 3 2

output:

2 5 3 1 4 

result:

ok OK!

Test #4:

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

input:

5 10 20
5 3 10 7 10

output:

5 3 4 1 2 

result:

ok OK!

Test #5:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

5 10 30
1 0 1 8 5

output:

2 1 3 5 4 

result:

ok OK!

Test #6:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

5 10 30
2 0 5 4 2

output:

2 1 5 4 3 

result:

ok OK!

Test #7:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

100 10 100
10 10 4 8 10 0 7 8 3 3 2 3 1 8 1 5 0 0 3 3 7 10 10 5 1 9 4 3 4 5 6 5 2 7 5 6 5 0 4 9 7 0 6 5 8 0 9 3 2 3 0 4 4 10 9 0 1 0 2 3 1 5 3 8 0 1 10 7 2 10 3 9 3 10 7 7 0 7 1 6 6 3 7 7 6 9 10 8 3 1 7 9 10 9 8 5 5 0 8 4

output:

impossible

result:

ok OK!

Test #8:

score: -100
Wrong Answer
time: 1ms
memory: 3588kb

input:

100 10 500
6 3 9 7 6 9 0 9 2 8 1 3 1 6 1 0 5 9 5 0 8 6 6 6 4 5 9 10 9 1 4 6 4 7 0 2 10 6 8 3 10 10 10 6 4 2 9 1 3 7 6 8 2 9 8 7 8 2 4 0 0 4 0 1 8 3 9 3 3 9 5 5 5 10 5 0 2 1 7 3 1 1 7 3 10 8 6 1 4 2 9 2 2 7 7 9 8 9 3 10

output:

impossible

result:

wrong answer Contestant printed 'impossible', but an answer existed.