QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#728917#880. Film Criticsgambit#WA 1ms5756kbC++171.9kb2024-11-09 16:11:452024-11-09 16:11:45

Judging History

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

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

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

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5628kb

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: 5756kb

input:

5 5 20
5 3 3 3 3

output:

impossible

result:

ok OK!

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3596kb

input:

5 10 20
6 1 9 3 2

output:

impossible

result:

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