QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#511755#8321. 季风TheRaptor90 106ms3860kbC++172.0kb2024-08-10 10:38:272024-08-10 10:38:27

Judging History

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

  • [2024-08-10 10:38:27]
  • 评测
  • 测评结果:90
  • 用时:106ms
  • 内存:3860kb
  • [2024-08-10 10:38:27]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
long long n,k,x,y,lo,hi,mid1,mid2,j;
__int128 a1,a2,v1,v2;
pair<long long,long long> arr[100005];
pair<long long,long long> net;
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--){
		long long in;
		long long ik,ix,iy;
		cin >> in >> ik >> ix >> iy;
		n=in,k=ik,x=ix,y=iy;
		net={0,0};
		for(int i=0; i<n; i++){
			long long a,b;
			cin >> a >> b;
			arr[i].first=a; arr[i].second=b;
			net.first+=arr[i].first;
			net.second+=arr[i].second;
			if(i) arr[i].first+=arr[i-1].first,arr[i].second+=arr[i-1].second;
		}
		if(x==0&&y==0){
			cout << 0 << '\n';
			continue;
		}
		long long iters[n];
		memset(iters,-1,sizeof(iters));
		for(int i=0; i<n; i++){
			lo=0,hi=1e13;
			while(hi-lo>2){
				mid1=(lo*2ll+hi)/3ll;
				mid2=(lo+hi*2ll)/3ll;
				//cout << lo << ' ' << mid1 << ' ' << mid2 << ' ' << hi << '\n';
				a1=x-(arr[i].first+(__int128)mid1*net.first),a2=y-(arr[i].second+(__int128)mid1*net.second);
				if(a1<0) a1=-a1;
				if(a2<0) a2=-a2;
				v1=a1+a2-(i+1+(__int128)mid1*n)*k;
				if(v1<=0){
					hi=mid2;
					continue;
				}
				a1=x-(arr[i].first+(__int128)mid2*net.first),a2=y-(arr[i].second+(__int128)mid2*net.second);
				if(a1<0) a1=-a1;
				if(a2<0) a2=-a2;
				v2=a1+a2-(i+1+(__int128)mid2*n)*k;
				if(v1<=0&&v2<=0) hi=mid2;
				else if(v2>v1) hi=mid2;
				else lo=mid1;
			}
			for(j=lo; j<=hi; j++){
				a1=x-(arr[i].first+(__int128)j*net.first),a2=y-(arr[i].second+(__int128)j*net.second);
				if(a1<0) a1=-a1;
				if(a2<0) a2=-a2;
				v1=a1+a2-(i+1+(__int128)j*n)*k;
				if(v1<=0){
					iters[i]=j;
					break;
				}
			}
		}
		long long ans=1e18+5;
		for(int i=0; i<n; i++){
			//cout << iters[i] << ' ';
			if(iters[i]!=-1) if(ans>iters[i]*n+i+1) ans=iters[i]*n+i+1;
		}
		if(ans>=(long long)1e18) cout << -1 << '\n';
		else cout << ans << '\n';
	}
}

詳細信息


Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 1ms
memory: 3560kb

input:

300
1 32286 -66773299 39159226
2655 14568
1 9900506 22484330 26135209
-33930 -9866575
1 669210 -40846340 -58419438
-529764 8866
1 74 -74443560 -78969527
-14 -37
1 473964 -91643319 -21680398
106817 243107
1 8543824 31629618 -37823687
1090776 4153469
1 16 -8109 -8410
-16 0
1 794120 -60084819 -21436725...

output:

2397
48619539
135
1227305
914
13
-1
96
28
1092928
42688085
-1
40791405
1
54608218
168
3415
13660
-1
53118060
19256086
17049
162101612
168026244
-1
147383845
16356862
158113199
367
19
-1
212
7
6677
13
56318408
0
-1
5
-1
107373214
7
176722
26
90888792
562
-1
3189099
655611
159239
1015616
60054
16874
8...

result:

ok 300 numbers

Test #2:

score: 10
Accepted
time: 1ms
memory: 3644kb

input:

300
1 0 14658671 -17744707
-19 23
1 0 -43777875 2899010
1318511 -388002
1 0 -39267054 -13736220
-19633527 -6868110
1 0 51104805 90132261
1473 -925
1 0 -30105792 20070528
48 -32
1 0 -73521410 -3106528
7939241 3095051
1 0 1934605 -4643052
-5 12
1 0 10981610 -30724102
5490805 -15362051
1 0 -8877616 887...

output:

-1
-1
2
-1
-1
-1
-1
2
-1
-1
-1
1
1
-1
1
-1
-1
504450
-1
383792
-1
2
-1
-1
-1
2
-1
1
551573
1
-1
1
-1
-1
-1
-1
290386
-1
-1
-1
-1
-1
1
-1
-1
122858
-1
1
-1
-1
1
-1
2
-1
1
1
-1
-1
558002
0
-1
1
-1
-1
-1
-1
-1
1
1
2
-1
2
-1
-1
-1
-1
2
-1
453621
2
2
-1
-1
127092
-1
-1
2
2
-1
198741
-1
-1
2
1
-1
-1
-1
2
...

result:

ok 300 numbers

Test #3:

score: 10
Accepted
time: 1ms
memory: 3632kb

input:

300
1 342739 0 84733186
0 0
1 1 -71236915 69825956
0 0
1 1 96944547 67493888
0 0
1 101010 10720443 27403069
0 0
1 0 -47050862 27820930
0 0
1 299851 -32954036 24041633
0 0
1 22039 16175909 -32970576
0 0
1 54 -92637795 -64306686
0 0
1 65 -42213950 -76922091
0 0
1 48846 0 20220443
0 0
1 4641 0 0
0 0
1 ...

output:

248
141062871
164438435
378
-1
191
2230
2906380
1832863
414
0
-1
21701397
25503860
3505
1570
43
56654328
1699
52308137
7951717
89151814
4773275
-1
243123
13
-1
69375
216700
58
114
457
35773753
1749173
-1
5825141
-1
28683350
117459
201508
64575587
323716
16610172
3959091
0
570
34498369
21969418
19289...

result:

ok 300 numbers

Test #4:

score: 10
Accepted
time: 1ms
memory: 3712kb

input:

300
1 491 19238896 24359756
2923207 -8745945
1 28452 -33430186 -3983771
18956 9495
1 1198593 -53848855 -4734461
93056 1105536
1 676 2931070 -9330910
52 -67
1 10 55228984 8970
-5 0
1 765812 2781176 64328480
-208 -223
1 0 -18744011 -35145767
-24 -45
1 251234 23812841 -10427626
-6279 -6797
1 996 -44886...

output:

-1
37413957
58583316
15424
11047591
88
-1
137
103025
69345443
2
-1
-1
4395
-1
-1
-1
-1
537956
149379205
-1
-1
25894733
440611
8990
3
-1
-1
-1
52207537
60700
420024
19149414
1
10
-1
52
-1
15156244
-1
320
-1
17647291
16255
0
3325
34073206
50713
-1
495
1
6
599074
3
-1
54344608
-1
30919544
-1
-1
11
-1
2...

result:

ok 300 numbers

Test #5:

score: 10
Accepted
time: 4ms
memory: 3656kb

input:

686
4 123 61343816 -81149292
43 62
-26 -93
68 31
-103 0
2 41 5546 -92990467
-40 0
-25 0
6 835927 -25588646 -89091109
644485 191442
677934 157993
398739 437187
762871 73056
776002 59925
553067 282859
2 542128 21060442 -2011
-23932 0
-25454 0
3 1 44172958 49903094
-1 0
-1 0
0 0
1 4491 18010618 -313236...

output:

1202474
10940708
344039265
41
282228156
5805
501513
282
12686985
113472955
115108557
12
17505368
209920957
7
14432
81544610
14
2
85768513
0
1396
4156
187149083
19428
1
6561618
1808
27
39193857
4
276
32462
251870741
1
862
66898
128
14266788
469
2
134
15193816
3881718
172988585
3
2159
129025368
137673...

result:

ok 686 numbers

Test #6:

score: 10
Accepted
time: 6ms
memory: 3624kb

input:

684
7 0 -4659965 65259689
-4659965 -99999977
0 0
0 0
0 0
4659965 99999979
0 0
0 0
1 0 18167938 67528693
18167938 67528693
7 0 -98200220 34188772
-98200220 34188772
-68294507 12668575
-28670964 -87244428
-98971553 90836074
74941179 92402443
10378449 63151034
-11200823 12733866
3 0 -80260647 -12683275...

output:

578408832
1
1
-1
1
-1
-1
-1
1
6
2128095
-1
1
1324125443
306230
-1
6
-1
5
-1
2804421
2
-1
-1
230055022
1
-1
-1
-1
1
-1
368563393
3
-1
1354128
1
732875
-1
-1
-1
1560100
-1
-1
-1
-1
-1
355038951
1779555255578
-1
-1
-1
103976047
-1
-1
12496201
-1
10
158771807
5
-1
6
-1
2
212817988
1346785
-1
-1
1
145106...

result:

ok 684 numbers

Test #7:

score: 10
Accepted
time: 4ms
memory: 3564kb

input:

667
6 22320 -47869922 -94574425
-35667 -912623
452472 -751486
42399 685787
-602148 221313
389986 58340
504503 896866
3 568 40479510 -78492210
-218 -454519
249230 -310323
-501776 -456425
4 96 -34634275 -41782650
450066 2475397
-1983097 1089604
-2006742 1395784
394497 -1700181
2 586988 87270830 324220...

output:

-1
-1
-1
239385813
1938779
6492421
-1
15294
291525169
10818277
49646093
202281
31128
1
-1
6053
-1
48575
-1
-1
12309331
-1
-1
4
2498
-1
464
-1
99423973
-1
-1
2337
-1
303530
205751489
37597620
101
4331250
11453
-1
-1
617
652
-1
171
0
-1
-1
245
2144
4142528904
0
251723
-1
22466088
127693
103361571
4289...

result:

ok 667 numbers

Test #8:

score: 10
Accepted
time: 58ms
memory: 3848kb

input:

5026
7 1536 96224177 3215062
-431 -1063
-930 207
392 -343
-151 -351
190 240
708 -222
1084 -118
2 2007 4875 8961
0 -1006
1282 725
3 74 6255 36271857
2 0
2 0
39 0
4 299644 51336139 54387095
-223835 -75808
-50044 -249599
-36180 -263463
-257793 -41851
5 87337 46515166 83800720
-45698 -41639
-38633 -4870...

output:

69860
6
607804
140964311
651579427
295842
781696
1860552
820363
97878227
875
10669352
113239787
41144
104
929275
4899340
228104447
79
29357925
433986768
1369
12933859
6292206
1
58638783
19199022
-1
6
136901931
9566917
3515420
64052003
9896
93383864
5847
1881477
19872258
2
3549
49
22157
199
204
26644...

result:

ok 5026 numbers

Test #9:

score: 10
Accepted
time: 106ms
memory: 3860kb

input:

5021
4 0 -12747354 40715188
8473127 -24739598
-4402460 47229129
-63791499 59230380
38500351 -16265125
1 0 13024199 16963243
-2413 -27747
4 0 85556443 48034225
66661568 99999993
18894875 99999991
-19570239 -99999994
-65986204 -99999993
1 0 -64373357 -92003118
3 0
3 0 -57596351 -55622531
-97485 -45744...

output:

5
-1
202621014
-1
-1
-1
-1
-1
-1
-1
903348426
1017644
3
-1
-1
-1
-1
3
9
-1
-1
-1
-1
131427163
3773967
-1
63606
4918116
341309620
-1
269616
307975448
425315146
2
1
-1
5270454
-1
411686418
-1
37840064
0
-1
-1
-1
1181692
10
4
855299912
-1
-1
-1
1392987
-1
-1
-1
-1
371539975
631281061
-1
6
-1
1
2331264
...

result:

ok 5021 numbers

Test #10:

score: 0
Time Limit Exceeded

input:

50122
5 25999922 8405 55768791
-1508111 -18663017
17765724 618297
-4046292 -11237396
-7742552 -12278384
6308331 3503946
2 204 -78318892 -78082051
582 -858
-620 -1217
2 33912059 -80164190 40071329
-4 -3
4 -3
1 281690 -6253970 14352972
-4363 328
5 11522477 13398456 -59393899
-173 -366
-221 -193
-484 1...

output:

4
-1
4
72
7
29646446
20208
9128183
6
165801675
13185324
11
5073737
-1
145
-1
-1
3534192
-1
156149623
65428515
614
-1
7
-1
6
808046
113618577
23028975
-1
20
10
1643705
51
-1
1195
2678557
-1
17991403
-1
391633112
-1
14045
6680
1790748528
158710
14
-1
74758279
130579777
14
-1
233685110
6
270663276
30
1...

result: