QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#235268 | #6561. Fail Fast | ugly2333 | WA | 0ms | 5980kb | C++20 | 752b | 2023-11-02 16:38:29 | 2023-11-02 16:38:30 |
Judging History
answer
//Δ_D
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double DB;
const int N = 111111;
const int B = 1e6;
int n,t[N],p[N],b[N],a[N],f[N],l[N],r[N],nx[N];
bool cmp(int i,int j){
return (LL)p[j]*t[i]<(LL)p[i]*t[j];
}
int fnd(int x){
if(f[x]==x)
return x;
return f[x]=fnd(f[x]);
}
void mrg(int x,int y){
x=fnd(x);
y=fnd(y);
nx[r[x]]=l[y];
r[x]=r[y];
f[y]=x;
}
int main(){
int i,x;
DB d;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d%lf%d",t+i,&d,b+i);
p[i]=d*B+0.5;
p[i]=B-p[i];
a[i]=i;
}
sort(a+1,a+n+1,cmp);
for(i=0;i<=n;i++)
f[i]=i,l[i]=i,r[i]=i,nx[i]=-1;
for(i=1;i<=n;i++)
mrg(b[a[i]],a[i]);
for(i=nx[0];i>=0;i=nx[i])
printf("%d\n",i);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3884kb
input:
4 100 0.5 0 200 0.1 1 10 0.5 2 10 0.9 0
output:
4 1 2 3
result:
ok correct
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 5980kb
input:
4 84 0.716 0 91 0.115 0 19 0.640 1 103 0.455 0
output:
2 4 1 3
result:
wrong answer your plan is not optimal