QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#569731#1146. Railiframe#30 1ms4004kbC++171.4kb2024-09-17 09:42:322024-09-17 09:42:32

Judging History

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

  • [2024-09-17 09:42:32]
  • 评测
  • 测评结果：30
  • 用时：1ms
  • 内存：4004kb
查看
  • [2024-09-17 09:42:32]
  • 提交

answer

#include "rail.h"

#include <algorithm>
#include <iostream>
#include <vector>
#include <set>

int alldist[100][100];
std::set<int> seen;
int n;

int closest(int i){
	int best = 4000000, res = -1;

	for(int j=0; j<n; ++j) if(!seen.count(j))
		if(alldist[i][j] < best) best = alldist[i][j], res = j;

	return res;
}

void findLocation(int N, int first, int location[], int stype[]){
	n = N;

	for(int i=0; i<n; ++i)
		for(int j=i+1; j<n; ++j)
			alldist[i][j] = getDistance(i, j),
				alldist[j][i] = alldist[i][j];

	location[0] = first, stype[0] = 1;

	seen.insert(0);
	int ldx = 0, rdx = closest(0), lmx = rdx, rmx = 0;
	location[rdx] = first + alldist[0][rdx];
	stype[rdx] = 2;
	seen.insert(rdx);

	for(int x=2; x<n; ++x){
//std::cout << "ldx, rdx, lmx, rmx: " << ldx << ' ' << rdx << ' ' << lmx << ' ' << rmx << '\n';

		int i = closest(ldx),
			d1 = alldist[ldx][i], d2 = alldist[rdx][i];

//std::cout << "found " << i << " (" << d1 << ' ' << d2 << ")\n";

		// left of rdx
		if(d1 - 2*(location[lmx]-location[ldx]) == d2 - (location[rdx]-location[ldx])){
			stype[i] = 1;
			location[i] = location[rdx] - d2;
			if(location[i] < location[ldx]) ldx = i;
		// right of rdx
		}else{
			stype[i] = 2;
			location[i] = location[ldx] + d1;
			rdx = i;
		}

		seen.insert(i);
	}

//for(int i=0; i<n; ++i) std::cout << stype[i] << ' ' << location[i] << '\n';
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 8
Accepted

Test #1:

score: 8
Accepted
time: 0ms
memory: 3884kb

input:

1
100
1 11
2 794
2 775
2 347
2 737
2 864
2 584
2 555
2 361
2 429
2 892
2 302
2 483
2 217
2 39
2 566
2 435
2 448
2 304
2 466
2 386
2 780
2 164
2 918
2 601
2 867
2 929
2 341
2 636
2 556
2 954
2 430
2 683
2 301
2 519
2 547
2 237
2 426
2 908
2 667
2 670
2 210
2 502
2 887
2 420
2 675
2 401
2 724
2 493
2 ...

output:

Correct

result:

ok

Test #2:

score: 8
Accepted
time: 1ms
memory: 3952kb

input:

1
100
1 13
2 768
2 165
2 101
2 185
2 678
2 145
2 865
2 650
2 769
2 985
2 756
2 236
2 973
2 688
2 522
2 654
2 316
2 598
2 901
2 274
2 547
2 744
2 511
2 684
2 331
2 822
2 757
2 198
2 85
2 526
2 363
2 186
2 711
2 393
2 683
2 928
2 43
2 805
2 914
2 152
2 239
2 840
2 916
2 893
2 509
2 514
2 561
2 410
2 7...

output:

Correct

result:

ok

Test #3:

score: 8
Accepted
time: 1ms
memory: 4004kb

input:

1
100
1 21
2 40
2 217
2 337
2 711
2 392
2 260
2 838
2 625
2 839
2 378
2 468
2 338
2 105
2 663
2 79
2 993
2 811
2 398
2 694
2 742
2 937
2 281
2 131
2 733
2 710
2 520
2 128
2 381
2 912
2 345
2 718
2 623
2 90
2 330
2 983
2 307
2 168
2 608
2 147
2 898
2 428
2 837
2 92
2 268
2 349
2 255
2 667
2 43
2 270
...

output:

Correct

result:

ok

Test #4:

score: 8
Accepted
time: 0ms
memory: 3864kb

input:

1
100
1 30
2 512
2 723
2 790
2 546
2 811
2 767
2 427
2 761
2 489
2 938
2 287
2 195
2 145
2 231
2 87
2 62
2 691
2 671
2 583
2 268
2 522
2 395
2 632
2 500
2 873
2 863
2 478
2 447
2 904
2 809
2 311
2 627
2 951
2 857
2 718
2 636
2 552
2 560
2 574
2 191
2 755
2 71
2 774
2 194
2 134
2 466
2 866
2 69
2 86
...

output:

Correct

result:

ok

Test #5:

score: 8
Accepted
time: 0ms
memory: 3924kb

input:

1
100
1 38
2 657
2 545
2 832
2 707
2 992
2 829
2 423
2 985
2 162
2 897
2 335
2 744
2 756
2 352
2 238
2 268
2 677
2 824
2 960
2 733
2 496
2 411
2 63
2 675
2 223
2 745
2 193
2 85
2 885
2 202
2 630
2 717
2 910
2 622
2 898
2 685
2 413
2 934
2 647
2 157
2 690
2 999
2 395
2 310
2 425
2 134
2 323
2 510
2 9...

output:

Correct

result:

ok

Test #6:

score: 8
Accepted
time: 1ms
memory: 3928kb

input:

1
100
1 12
2 669
2 901
2 133
2 896
2 738
2 776
2 44
2 134
2 154
2 29
2 638
2 937
2 874
2 235
2 397
2 779
2 709
2 588
2 701
2 324
2 965
2 865
2 251
2 710
2 715
2 689
2 249
2 174
2 551
2 270
2 427
2 684
2 518
2 165
2 812
2 914
2 298
2 68
2 899
2 936
2 357
2 773
2 524
2 755
2 552
2 233
2 343
2 605
2 90...

output:

Correct

result:

ok

Test #7:

score: 8
Accepted
time: 1ms
memory: 3924kb

input:

1
100
1 47
2 198
2 904
2 942
2 714
2 510
2 431
2 594
2 690
2 75
2 449
2 786
2 920
2 277
2 731
2 742
2 136
2 760
2 633
2 224
2 637
2 927
2 959
2 222
2 657
2 474
2 611
2 401
2 307
2 759
2 952
2 563
2 701
2 666
2 425
2 484
2 613
2 115
2 505
2 688
2 564
2 292
2 609
2 194
2 375
2 703
2 330
2 336
2 555
2 ...

output:

Correct

result:

ok

Test #8:

score: 8
Accepted
time: 1ms
memory: 3920kb

input:

1
100
1 7
2 631
2 253
2 535
2 16
2 311
2 891
2 250
2 698
2 843
2 525
2 43
2 740
2 429
2 610
2 643
2 276
2 529
2 243
2 174
2 229
2 537
2 288
2 685
2 459
2 823
2 878
2 72
2 759
2 663
2 573
2 366
2 294
2 179
2 842
2 144
2 265
2 541
2 340
2 791
2 936
2 432
2 572
2 898
2 75
2 201
2 427
2 670
2 375
2 8
2 ...

output:

Correct

result:

ok

Test #9:

score: 8
Accepted
time: 0ms
memory: 3948kb

input:

1
100
1 34
2 445
2 537
2 285
2 903
2 312
2 975
2 250
2 885
2 125
2 818
2 557
2 560
2 525
2 400
2 227
2 577
2 50
2 340
2 748
2 390
2 370
2 508
2 663
2 150
2 144
2 923
2 741
2 746
2 909
2 100
2 191
2 446
2 385
2 759
2 713
2 696
2 996
2 838
2 515
2 353
2 747
2 75
2 879
2 499
2 654
2 456
2 550
2 994
2 9...

output:

Correct

result:

ok

Test #10:

score: 8
Accepted
time: 1ms
memory: 3888kb

input:

1
100
1 31
2 325
2 179
2 190
2 113
2 350
2 720
2 553
2 712
2 465
2 524
2 657
2 671
2 665
2 390
2 348
2 620
2 901
2 342
2 116
2 649
2 724
2 473
2 789
2 618
2 890
2 449
2 334
2 669
2 232
2 363
2 346
2 763
2 554
2 459
2 114
2 626
2 178
2 91
2 889
2 180
2 100
2 912
2 197
2 843
2 260
2 170
2 96
2 954
2 2...

output:

Correct

result:

ok

Subtask #2:

score: 22
Accepted

Test #11:

score: 22
Accepted
time: 1ms
memory: 3988kb

input:

2
100
1 7327
1 116
2 9993
1 2736
1 6502
1 4106
1 6326
2 8055
1 6767
1 388
2 7645
1 1780
1 6159
2 7738
1 3706
1 3476
2 9549
2 7564
1 2401
1 6353
2 8829
1 945
1 606
1 4664
2 9585
2 7499
1 6703
1 3229
1 1382
2 8286
1 6805
1 351
1 793
1 1641
1 3087
1 3647
1 2099
2 9414
1 1703
2 8866
2 9802
2 9348
1 6999...

output:

Correct

result:

ok

Test #12:

score: 22
Accepted
time: 1ms
memory: 3924kb

input:

2
100
1 1901
1 411
2 9673
2 2260
2 8712
2 7185
2 5395
1 1269
2 3469
2 2852
2 2413
2 7783
2 5977
1 1813
2 6087
2 8802
2 3390
2 5039
2 2569
2 4694
2 4812
2 5704
1 586
2 9645
2 4978
2 8969
1 1204
2 2191
2 5943
1 689
2 7955
2 9270
2 6567
2 4334
2 3816
2 8314
2 1955
2 7285
1 1166
1 720
1 1420
2 3495
2 25...

output:

Correct

result:

ok

Test #13:

score: 22
Accepted
time: 1ms
memory: 3992kb

input:

2
100
1 1415
1 437
2 9880
2 3580
2 7655
2 6320
2 2670
2 4305
2 4632
2 7346
2 9814
2 9368
2 5374
2 2260
2 3386
2 4316
2 3357
2 7526
2 7175
2 7817
2 3513
2 4225
2 2655
2 5494
2 8763
2 9731
2 5138
1 1142
2 4612
2 4541
2 5931
1 584
2 9734
2 9511
2 8239
2 2406
2 2182
2 2545
2 7039
2 5880
2 8711
2 6407
1 ...

output:

Correct

result:

ok

Test #14:

score: 22
Accepted
time: 0ms
memory: 3888kb

input:

2
100
1 2038
1 225
2 9673
2 7337
2 5096
2 4800
2 6802
2 7455
2 4099
2 4191
1 1709
1 1103
2 5684
2 6557
2 2721
2 5856
2 4968
2 7917
1 1993
2 9660
2 5644
1 1917
2 3549
1 1585
2 6539
1 1260
2 7557
1 947
1 1881
2 2710
2 8560
2 2742
2 3714
2 7543
2 6868
2 7464
1 1642
1 1060
2 5525
2 9097
1 1122
1 1210
2 ...

output:

Correct

result:

ok

Test #15:

score: 22
Accepted
time: 0ms
memory: 3880kb

input:

2
100
1 7252
1 151
2 9808
1 3057
1 4522
1 5639
1 6094
2 9254
2 8858
1 5939
2 8584
1 7218
2 8112
1 4381
1 3678
1 1662
1 1899
1 5713
1 3520
1 4699
2 8353
1 6579
2 9583
2 8042
1 2588
1 4762
1 1522
1 6720
1 4373
1 896
2 7340
1 4376
1 3940
1 4275
2 7433
1 4814
1 6266
1 4068
1 5124
1 5819
1 2652
1 2343
1 ...

output:

Correct

result:

ok

Test #16:

score: 22
Accepted
time: 1ms
memory: 3884kb

input:

2
100
1 3294
1 357
2 9844
2 9740
2 5435
2 9577
1 864
2 5781
1 851
2 3821
2 4905
2 4712
2 4633
2 9524
2 5642
1 1230
2 7759
2 3568
2 8011
1 3247
2 9641
2 4309
2 9125
1 2458
1 1907
2 9538
2 5194
1 2491
2 3399
2 7903
1 1500
2 9700
2 7643
2 6935
2 5630
2 4860
2 9068
2 6481
2 8681
2 3973
2 7546
2 9666
2 4...

output:

Correct

result:

ok

Test #17:

score: 22
Accepted
time: 1ms
memory: 3868kb

input:

2
100
1 4873
1 217
2 9694
1 2520
2 5783
2 9383
2 6576
1 1423
2 5313
2 9437
2 5334
1 3222
1 3794
1 1001
2 6338
2 5692
1 1460
1 334
2 6029
1 3147
2 7309
2 6978
2 6554
2 8726
1 1030
1 2838
2 7012
1 2116
2 6742
2 6081
1 275
1 3772
2 4954
2 6058
2 9508
2 7882
1 3834
1 4821
2 7685
1 3271
2 7259
1 3417
2 6...

output:

Correct

result:

ok

Test #18:

score: 22
Accepted
time: 1ms
memory: 4004kb

input:

2
100
1 2614
1 286
2 9704
1 1272
2 8020
2 9591
2 5027
2 2725
2 3140
1 2235
1 2453
1 1187
2 3012
1 1545
2 4515
2 7054
2 5093
2 8592
1 1445
1 2292
2 3280
2 8146
2 5169
2 6695
1 2267
2 4584
1 1167
2 3103
2 4766
1 689
2 2741
2 4014
2 4434
2 8183
2 9041
2 3512
1 1323
2 7628
2 5965
1 2510
1 640
1 2550
2 4...

output:

Correct

result:

ok

Test #19:

score: 22
Accepted
time: 1ms
memory: 4000kb

input:

2
100
1 6399
1 178
2 9675
1 3942
1 3328
1 4149
1 3640
1 6214
2 8677
1 2608
1 3755
1 1524
1 5766
1 3158
1 1165
1 4695
2 6866
1 4729
1 529
1 4207
2 6663
2 7778
1 3203
1 614
2 8457
1 5472
1 5182
1 3799
2 9316
1 4361
1 2311
1 4655
2 6460
1 1992
2 8804
1 2135
1 1371
1 5130
1 1095
1 1478
2 6654
2 6862
1 4...

output:

Correct

result:

ok

Test #20:

score: 22
Accepted
time: 1ms
memory: 3888kb

input:

2
100
1 7653
1 473
2 9622
2 9239
1 4765
1 4086
1 4598
1 736
1 6988
1 5711
1 3386
1 3780
1 6603
1 5591
1 6070
1 6290
1 894
1 1714
1 3094
1 4744
1 6656
1 6707
1 910
1 5948
2 8821
1 7254
1 2407
2 7928
1 1157
1 5232
1 7306
1 7482
1 1219
1 6545
2 8599
1 5305
1 7495
1 5687
2 8645
1 3207
1 5688
2 8383
1 33...

output:

Correct

result:

ok

Subtask #3:

score: 0
Runtime Error

Test #21:

score: 0
Runtime Error

input:

3
5000
1 763228
1 39310
2 962072
2 203549
1 85439
2 414565
2 78225
1 185073
2 174996
2 386604
1 662313
2 96651
1 271323
2 556033
1 788441
1 717148
1 404737
2 197742
2 760887
1 549658
2 713177
1 156708
1 858133
1 166177
1 809643
2 365041
1 73222
2 706708
2 296516
1 861386
1 782475
2 167675
1 100665
1...

output:

Unauthorized output

result:

Subtask #4:

score: 0
Runtime Error

Test #31:

score: 0
Runtime Error

input:

3
5000
1 763228
1 39310
2 962072
2 203549
1 85439
2 414565
2 78225
1 185073
2 174996
2 386604
1 662313
2 96651
1 271323
2 556033
1 788441
1 717148
1 404737
2 197742
2 760887
1 549658
2 713177
1 156708
1 858133
1 166177
1 809643
2 365041
1 73222
2 706708
2 296516
1 861386
1 782475
2 167675
1 100665
1...

output:

Unauthorized output

result:
English 繁體中文 简体中文

Server Time: 2024-12-05 06:28:36 | OpenSource Project