QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#728877 | #880. Film Critics | gambit# | TL | 1ms | 5700kb | C++17 | 1.5kb | 2024-11-09 16:08:26 | 2024-11-09 16:08:27 |
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);
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;
}
详细
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