QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#609594#9427. Collect the CoinsFork512HzWA 211ms19248kbC++201.3kb2024-10-04 13:30:592024-10-04 13:31:00

Judging History

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

  • [2024-11-06 15:56:27]
  • hack成功,自动添加数据
  • (/hack/1139)
  • [2024-10-04 13:31:00]
  • 评测
  • 测评结果:WA
  • 用时:211ms
  • 内存:19248kb
  • [2024-10-04 13:30:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pii;
//#define DEBUG

#ifdef DEBUG
const ll N = 1010;
#endif
#ifndef DEBUG
const ll N = 1001000;
#endif
pii a[N];
ll n;
bool chk(ll d)
{
	ll pt, l1, r1, l2, r2;
	pt = 0;
	l1 = l2 = -1E12;
	r1 = r2 = 1E12;
	for(ll i=0; i<n; i++)
	{
		ll dist = d * (a[i].first - pt);
		l1 -= dist; l2 -= dist;
		r1 += dist; r2 += dist;
		ll rx = -1E12, lx = 1E12;
		if (a[i].second >= l1 && a[i].second <= r1)
			rx = max(rx, r2), lx = min(lx, l2);
		if (a[i].second >= l2 && a[i].second <= r2)
			rx = max(rx, r1), lx = min(lx, l1);
		if(lx > rx) return 0;
		pt = a[i].first;
		l1 = a[i].second, r1 = a[i].second;
		l2 = lx, r2 = rx;
	}
	return 1;
}
int main()
{
	#ifndef DEBUG
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	#endif
	#ifdef DEBUG
	freopen("1.txt", "r", stdin);
	#endif
	ll z=  1;
	cin >> z;
	while(z--)
	{
		cin >> n;
		
		for(ll i=0; i<n; i++)
		{
			ll x, y;
			cin >> x >> y;
			a[i] = {x, y};
		}
		ll lb = 0, rb = 100000001;
		while(lb < rb)
		{
			ll mid = (lb+rb) / 2;
			if(chk(mid)) rb = mid;
			else lb = mid+1;
		}
		if(lb == 100000001) cout << -1 << '\n';
		else cout << lb << '\n';
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3700kb

input:

3
5
1 1
3 7
3 4
4 3
5 10
1
10 100
3
10 100
10 1000
10 10000

output:

2
0
-1

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 11ms
memory: 3860kb

input:

1135
2
6 5
8 8
8
2 9
2 10
4 4
5 3
6 2
6 8
8 2
8 7
1
9 1
6
4 6
6 1
6 2
9 10
10 1
10 7
5
1 6
2 5
6 7
8 6
10 3
8
1 10
5 4
5 7
6 1
6 6
8 4
9 1
9 4
8
1 1
1 3
2 9
3 3
5 9
6 10
9 7
10 7
3
5 8
6 6
10 6
7
2 9
4 7
5 10
6 3
6 7
8 9
10 1
6
1 4
2 8
5 9
7 10
9 1
10 5
9
2 7
4 5
5 9
6 10
7 4
9 4
9 9
10 3
10 7
1
3 1...

output:

0
3
0
3
1
3
6
0
3
2
2
0
2
5
0
1
5
1
2
0
0
0
1
4
2
0
2
1
3
0
3
2
3
2
5
3
1
1
0
1
1
1
0
2
0
1
0
1
0
2
1
0
2
3
4
4
1
1
1
0
1
3
0
1
4
4
3
0
0
2
2
6
4
2
1
0
0
1
0
2
1
2
0
1
1
3
0
0
1
2
0
3
0
2
2
2
1
0
0
0
5
1
2
0
6
1
1
1
2
2
2
0
3
1
4
3
6
0
8
1
1
3
0
2
2
4
1
1
0
0
0
7
2
2
1
0
0
3
1
2
1
1
2
5
3
0
3
3
3
5
...

result:

ok 1135 lines

Test #3:

score: 0
Accepted
time: 211ms
memory: 19196kb

input:

1
1000000
2 57841
2 357142
3 496329
3 545446
4 503408
4 590762
5 78281
6 196926
6 349414
7 200245
8 953412
11 616898
12 592065
13 945945
15 20908
15 852722
16 221184
16 401521
17 884478
18 186072
18 931445
19 833560
20 314177
21 138453
21 731965
22 172104
23 595921
25 372617
27 545759
28 977029
30 4...

output:

994024

result:

ok single line: '994024'

Test #4:

score: 0
Accepted
time: 147ms
memory: 19248kb

input:

1
1000000
6 1991827
13 8125243
19 22493
24 4282711
28 356362
39 765152
41 6737899
44 8549464
57 4530192
64 7201376
67 6695629
70 3830504
70 6658581
71 4591382
71 8349070
75 2107828
76 4073563
81 2712838
92 1391185
95 4663781
102 5986957
113 8423636
118 7826607
122 1171556
122 3118750
160 938066
162 ...

output:

9609125

result:

ok single line: '9609125'

Test #5:

score: -100
Wrong Answer
time: 110ms
memory: 19180kb

input:

1
1000000
108 565196036
597 561009880
1007 831705109
2597 55966094
2869 765993518
3025 202191673
3283 237167825
3410 829643653
4879 960747182
7284 679152790
8765 64201585
8899 97619554
9320 713144607
9519 991746776
9913 346063307
11161 970513525
11256 975123550
12073 778562963
14286 206857559
15803 ...

output:

-1

result:

wrong answer 1st lines differ - expected: '268764694', found: '-1'