QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#575116#5513. Advertisement 2ModyKachef23 0ms3876kbC++231.2kb2024-09-19 10:38:552024-09-19 10:38:59

Judging History

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

  • [2024-09-19 10:38:59]
  • 评测
  • 测评结果:23
  • 用时:0ms
  • 内存:3876kb
  • [2024-09-19 10:38:55]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long 

int n;
int x[20] , e[20]; 
int ans =1e18 ;

void brute(int i , int msk , int cnt){
    if (i == n){
        if (msk == (1<<n)-1) ans = min(ans , cnt); 
        return;
    }
    brute(i+1 , msk , cnt);
    int nmsk = msk;
    for (int j = 0 ; j < n;  j++){
        if (abs(x[i]-x[j]) <= e[i]-e[j]) nmsk|=(1<<j); 
    }
    brute(i+1 , nmsk , cnt+1); 
}

bool adj[(int)1001][1001]; 

signed main(){
    cin >> n;
    vector<pair<int , int>> v(1); 
    for (int i = 1 ; i<=  n; i++){
        cin >> x[i] >> e[i]; 
        v.push_back({e[i] , x[i]}); 
    }    
    sort(v.begin()+1 , v.end() , greater<>());
    for (int i = 1 ; i <= n ; i++){
        e[i] = v[i].first;
        x[i] = v[i].second; 
    }
    for (int i = 1 ; i <= n ; i++){
        for (int j = 1 ; j <= n ; j++){
            if (abs(x[i] - x[j]) <= e[i] - e[j]) adj[i][j] = 1;  
        }
    }
    int ans = 0; 
    bool vis[(int)n+1] = {}; 
    for (int i = 1 ; i <= n ; i++){
        if (vis[i]) continue;
        ans++; 
        for (int j = 1 ; j <= n ; j++){
            if (adj[i][j]) vis[j] = 1; 
        }
    }
    cout << ans; 
}

// | X[i] - X[j] | <= E[i]

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 0
Runtime Error

input:

128800
9199612 51970557
152303663 51970557
658020283 51970557
305169975 51970557
647937895 51970557
162441995 51970557
664350717 51970557
128813867 51970557
815800777 51970557
422654970 51970557
5325941 51970557
919605369 51970557
775929588 51970557
957253076 51970557
441558150 51970557
730596606 51...

output:


result:


Subtask #2:

score: 23
Accepted

Test #9:

score: 23
Accepted
time: 0ms
memory: 3508kb

input:

3
231636235 354089104
228392707 930073348
587735804 575683740

output:

2

result:

ok single line: '2'

Test #10:

score: 23
Accepted
time: 0ms
memory: 3656kb

input:

2
44803615 325394921
960290812 913042209

output:

2

result:

ok single line: '2'

Test #11:

score: 23
Accepted
time: 0ms
memory: 3832kb

input:

16
358962202 959156048
292228464 457977429
286504790 688097514
10235865 287544591
543037593 223202351
281739475 678894125
340538778 135823278
523049160 699098750
632448464 27592532
678838907 280282008
232201876 610344934
372201424 580697311
534022553 149440684
396794335 231096472
386573567 674797431...

output:

1

result:

ok single line: '1'

Test #12:

score: 23
Accepted
time: 0ms
memory: 3796kb

input:

16
991478601 586353863
727677584 413218995
848190574 721774939
337154838 587621991
326181535 330546474
885714927 902337871
321925936 254469460
389203245 713455202
269046070 768322315
614176036 221983130
199199666 945777980
333801969 632191948
426251079 645513607
230568723 962651792
817646607 6209057...

output:

3

result:

ok single line: '3'

Test #13:

score: 23
Accepted
time: 0ms
memory: 3676kb

input:

16
259716405 81082178
865953834 204158972
701456061 326495636
534687353 313425011
649435476 973258810
655435866 100458236
842552753 181656857
473079491 116991153
2508936 173927847
405046133 391068638
302771733 495790124
35966251 515357032
272182509 442914085
348221691 938487780
990378664 943640991
2...

output:

3

result:

ok single line: '3'

Test #14:

score: 23
Accepted
time: 0ms
memory: 3872kb

input:

16
750613470 787418986
170979548 365164484
538034539 608096710
860751449 225707539
484373402 547435035
940351136 194668865
912301765 93898337
458896779 93991117
604496090 637207865
887366195 906979783
557233961 724709014
79115098 854994617
46404315 744331005
915505818 998759323
415682887 70000722
24...

output:

3

result:

ok single line: '3'

Test #15:

score: 23
Accepted
time: 0ms
memory: 3828kb

input:

16
4 4
12 10
7 1
14 9
5 1
7 4
6 2
11 12
11 8
7 7
1 16
1 7
7 11
10 1
5 9
16 14

output:

4

result:

ok single line: '4'

Test #16:

score: 23
Accepted
time: 0ms
memory: 3636kb

input:

16
14 11
15 15
2 2
9 11
12 3
1 2
5 6
3 8
11 6
6 8
16 8
7 13
14 15
3 9
11 13
5 12

output:

5

result:

ok single line: '5'

Test #17:

score: 23
Accepted
time: 0ms
memory: 3632kb

input:

16
658226792 613575956
913043019 676526283
924694003 969774080
131921851 969262560
105914395 172872671
871392287 24274699
165576907 264780282
21100418 923953766
624953565 298094995
530525465 571735572
303994035 463877704
809045037 954969312
573298570 667280152
101731595 308198144
530525465 554053924...

output:

4

result:

ok single line: '4'

Test #18:

score: 23
Accepted
time: 0ms
memory: 3572kb

input:

16
41059816 221337331
83624488 326689210
104858222 385883720
404619929 86122013
634866221 167428105
333552651 862965438
254015874 434293389
326707158 747676654
450873607 69675126
443566588 47175354
634866221 532361838
611136129 921561993
859951785 430454936
166920241 409984963
634866221 611154765
45...

output:

3

result:

ok single line: '3'

Test #19:

score: 23
Accepted
time: 0ms
memory: 3796kb

input:

16
936303273 104982189
63575875 559779062
796436147 569999950
688713338 829608600
54555214 355061353
213704891 195911676
392107461 17509106
922762043 308356453
301430216 797633403
991422839 48500064
287802278 121814289
172394178 237222389
688713338 135188143
633629597 30839372
564890892 276172238
68...

output:

2

result:

ok single line: '2'

Test #20:

score: 23
Accepted
time: 0ms
memory: 3580kb

input:

16
357789622 471544489
155990470 269745335
398736883 512491748
873381940 675455361
693445929 807200795
819730274 729107023
609830064 723584926
909092208 639745095
717541218 831296078
384480802 498235672
255651917 369406780
368140959 481895828
478227819 591982683
939144255 609693050
40813895 15456875...

output:

8

result:

ok single line: '8'

Test #21:

score: 23
Accepted
time: 0ms
memory: 3632kb

input:

16
675342555 193353548
971242060 11
536846016 331850093
836414885 32281218
186149471 245161906
928775073 8
750901538 117794571
828962292 39733819
911644130 4
588800258 279895844
296580159 355592604
802169978 66526131
273197350 332209795
404841833 463854267
109933975 168946414
885435693 10

output:

8

result:

ok single line: '8'

Test #22:

score: 23
Accepted
time: 0ms
memory: 3876kb

input:

16
953262221 724605861
954831951 723036137
687777113 990090964
350416397 707784111
683740929 986054786
599178111 901491972
585162338 898281936
692323709 985544379
525093723 882461438
557373498 914741210
584165982 899278291
203656094 561023816
854238442 823629640
278833052 636200772
577917599 8941971...

output:

11

result:

ok single line: '11'

Test #23:

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

input:

16
254025469 306467199
427159560 479601287
593614318 571659026
928541548 665993610
896411728 698123427
892481215 694192919
63151125 115592847
986723922 607811241
499586562 552028289
556415811 608857532
293855819 346297542
128409262 180850989
763105705 574193679
238718076 291159807
101875941 15431766...

output:

11

result:

ok single line: '11'

Subtask #3:

score: 0
Runtime Error

Dependency #2:

100%
Accepted

Test #24:

score: 0
Runtime Error

input:

969
40204287 456937654
286592935 721399309
55601488 988576547
98308463 233903868
372607004 249568606
671927697 865318354
859455683 411992226
204457272 180441733
613470249 214734085
527175838 697833267
358494964 102583786
46530087 943520460
253765364 851932504
364762894 237641176
205684131 478882150
...

output:


result:


Subtask #4:

score: 0
Skipped

Dependency #1:

0%