QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #278621 | #7750. Revenge on My Boss | KomejiNora | TL | 0ms | 0kb | C++14 | 1.1kb | 2023-12-07 18:39:41 | 2023-12-07 18:39:41 |
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int n,a[N],b[N],c[N],B;
int d[N],e[N];
int p[N];
bool cmp(int x,int y) {
if(d[x]<0&&d[y]<0) return e[x]>e[y];
if(d[x]<0) return 1;
if(d[y]<0) return 0;
if(d[x]+e[x]!=d[y]+e[y]) return d[x]+e[x]<d[y]+e[y];
return e[x]<e[y];
}
bool check(int t) {
for(int i=1;i<=n;i++) {
p[i]=i;
d[i]=a[i]-b[i];
e[i]=t/c[i]-a[i]-B;
}
sort(p+1,p+n+1,cmp);
int sum=0;
for(int i=1;i<=n;i++) {
int x=p[i];
if(sum>e[x]) return false;
sum+=d[x];
}
return true;
}
signed main() {
int T;scanf("ll%d",&T);
while(T--) {
scanf("%lld",&n);B=0;
for(int i=1;i<=n;i++) scanf("%lld%lld%lld",&a[i],&b[i],&c[i]),B+=b[i];
int l=0,r=1e9,ans,mid;
while(l<=r) {
mid=(l+r)>>1;
if(check(mid)) {
ans=mid;
l=mid+1;
}
else r=mid-1;
}
check(ans);
for(int i=1;i<=n;i++) printf("%lld ",p[i]);puts("");
}
return 0;
}
详细
Test #1:
score: 0
Time Limit Exceeded
input:
2 4 1 1 4 5 1 5 1 9 1 9 8 1 9 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 8 3 2 7
output:
2 1 1 5 4 2 3 5 1 2 4 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 ...