QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#312530#8137. 'Ello, and What Are You After, Then?Kevin5307WA 1329ms5096kbC++232.1kb2024-01-23 22:54:482024-01-23 22:54:48

Judging History

This is the latest submission verdict.

  • [2024-01-23 22:54:48]
  • Judged
  • Verdict: WA
  • Time: 1329ms
  • Memory: 5096kb
  • [2024-01-23 22:54:48]
  • Submitted

answer

//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
int b,c,s,n;
vector<array<int,3>> skill[1010];
int gen(int ind,double val,double cost)
{
	vector<array<double,3>> vec;
	for(auto arr:skill[ind])
	{
		double cost1=1.0*(arr[2]-val)*arr[1]+c*cost;
		double cost2=-s*cost;
		if(cost1>cost2)
			vec.pb(array<double,3>{cost1*arr[0],(1.0*(arr[2]-val)*arr[1])*arr[0],c*arr[0]});
		else
			vec.pb(array<double,3>{cost2*arr[0],0,-s*arr[0]});
	}
	rsrt(vec);
	int cnt=0;
	while(sz(vec)&&cnt<b&&vec.back()[0]<0)
	{
		cnt++;
		vec.pop_back();
	}
	double A=0,B=0;
	for(auto arr:vec)
	{
		A+=arr[1];
		B+=arr[2];
	}
	double sum=0;
	for(auto arr:vec)
		sum+=arr[0];
	if(sum<0) return 0;
	if(A>0&&B>0)
		return 1;
	if(A>0) return 2;
	return 4;
}
bool check(double val)
{
	double l=1e-4,r=1e4;
	for(int i=0;i<30;i++)
	{
		double mid=sqrt(l*r);
		int msk=0;
		for(int j=1;j<=n;j++)
			msk|=gen(j,val,mid);
		if(msk&1)
			return true;
		if(msk&2)
			if(msk&4)
				return true;
		if(!msk)
			return false;
		if(msk&2)
			l=mid;
		else
			r=mid;
	}
	return true;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>b>>c>>s>>n;
	for(int i=1;i<=n;i++)
	{
		int m;
		cin>>m;
		while(m--)
		{
			int f,t,e;
			cin>>f>>t>>e;
			skill[i].pb(array<int,3>{f,t,e});
		}
	}
	double l=0,r=1e5;
	for(int i=0;i<50;i++)
	{
		double mid=(l+r)/2;
		if(check(mid))
			l=mid;
		else
			r=mid;
	}
	printf("%.20lf\n",l);
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3740kb

input:

0 1 6
2
1
1 1 1
2
1 10 1
1 10 10

output:

7.00000001367939717056

result:

ok found '7.0000000', expected '7.0000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 4020kb

input:

2 1 2
1
4
10 2 1
10 1 1
1 10 1
1 1 10

output:

5.90909093309832655905

result:

ok found '5.9090909', expected '5.9090909', error '0.0000000'

Test #3:

score: 0
Accepted
time: 766ms
memory: 4108kb

input:

14 1000 1000
1000
30
113 80 1188
92 145 1074
130 56 1296
139 102 1142
60 76 1317
128 126 1208
73 120 1155
91 89 1197
115 64 979
80 118 592
110 97 556
83 105 578
94 51 848
98 134 757
107 138 1038
105 143 892
92 72 893
88 103 961
87 148 879
105 84 823
85 134 607
100 82 1084
199 58 801
138 85 743
214 1...

output:

1453.36457910127955983626

result:

ok found '1453.3645791', expected '1453.3645790', error '0.0000000'

Test #4:

score: 0
Accepted
time: 738ms
memory: 5096kb

input:

8720 713 168
1
30000
1 186 5272
2 53 5132
2 124 5529
2 186 5052
2 82 5342
2 178 5027
1 74 5271
2 154 5506
1 185 5225
2 60 5068
2 85 5179
1 193 5231
1 94 5469
2 168 5317
2 142 5153
2 44 5083
2 71 5318
2 53 5325
1 68 5051
2 53 5424
2 150 5125
2 122 5371
2 126 5171
2 39 5315
2 57 5193
1 130 5203
2 179 ...

output:

5276.12718345551456877729

result:

ok found '5276.1271835', expected '5276.1271835', error '0.0000000'

Test #5:

score: 0
Accepted
time: 1120ms
memory: 5028kb

input:

19121 34 288
1
30000
8 213 5200
10 169 5148
6 228 5033
11 83 5151
10 98 5200
10 228 5124
7 111 5091
9 218 5114
9 115 5198
10 142 5027
10 221 5105
7 201 5191
10 153 5002
7 130 5186
11 131 5116
10 115 5030
9 124 5053
9 225 5039
10 100 5109
9 170 5202
9 220 5125
11 187 5056
12 115 5062
9 218 5103
6 139...

output:

5092.99345214886488975026

result:

ok found '5092.9934521', expected '5092.9934521', error '0.0000000'

Test #6:

score: 0
Accepted
time: 1329ms
memory: 4052kb

input:

6753 181 9
3
10000
13 948 5040
22 140 5020
10 265 5037
24 1021 5027
12 841 5081
15 202 5034
15 606 5052
11 140 5040
12 1071 5025
9 1045 5022
23 504 5026
19 1213 5085
24 839 5075
12 549 5080
23 643 5025
15 434 5070
25 578 5007
10 132 5030
16 335 5034
21 329 5085
8 239 5084
22 447 5082
26 168 5004
22 ...

output:

5067.16990316400369920302

result:

ok found '5067.1699032', expected '5067.1699032', error '0.0000000'

Test #7:

score: -100
Wrong Answer
time: 794ms
memory: 4292kb

input:

0 3 4
1000
30
36 868 5560
34 896 5226
34 867 5493
32 818 5036
34 1012 5202
37 1136 5475
36 1110 5146
30 1128 5199
33 912 5218
33 903 5398
36 786 5018
37 744 5551
30 997 5120
35 826 5484
32 1133 5300
35 783 5294
32 840 5119
36 958 5186
36 798 5115
37 981 5482
37 792 5390
32 888 5120
31 794 5065
35 99...

output:

5571.34676141979252861347

result:

wrong answer 1st numbers differ - expected: '5560.1314972', found: '5571.3467614', error = '0.0020171'