QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#728942 | #880. Film Critics | gambit# | WA | 1ms | 5744kb | C++17 | 2.0kb | 2024-11-09 16:15:00 | 2024-11-09 16:15:00 |
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=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.