QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#235268#6561. Fail Fastugly2333WA 0ms5980kbC++20752b2023-11-02 16:38:292023-11-02 16:38:30

Judging History

你现在查看的是最新测评结果

  • [2023-11-02 16:38:30]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:5980kb
  • [2023-11-02 16:38:29]
  • 提交

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