QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#728917 | #880. Film Critics | gambit# | WA | 1ms | 5756kb | C++17 | 1.9kb | 2024-11-09 16:11:45 | 2024-11-09 16:11:45 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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.