QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#711295#3189. Finding Lines_dsmoi_AC ✓401ms4904kbC++142.3kb2024-11-05 09:05:322024-11-05 09:05:34

Judging History

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

  • [2024-11-05 09:05:34]
  • 评测
  • 测评结果:AC
  • 用时:401ms
  • 内存:4904kb
  • [2024-11-05 09:05:32]
  • 提交

answer

#include"bits/stdc++.h"
using namespace std;
#define rep(i, a, b) for(ll i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define endl "\n"
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;


template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
typedef Point P;
T x, y;
explicit Point(T x=0, T y=0) : x(x), y(y) {}
bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
P operator+(P p) const { return P(x+p.x, y+p.y); }
P operator-(P p) const { return P(x-p.x, y-p.y); }
P operator*(T d) const { return P(x*d, y*d); }
P operator/(T d) const { return P(x/d, y/d); }
T dot(P p) const { return x*p.x + y*p.y; }
T cross(P p) const { return x*p.y - y*p.x; }
T cross(P a, P b) const { return (a-*this).cross(b-*this); }
T dist2() const { return x*x + y*y; }
double dist() const { return sqrt((double)dist2()); }
// angle to x=axis in interval [=pi , pi ]
double angle() const { return atan2(y, x); }
P unit() const { return *this/dist(); } // makes d i s t ()=1
P perp() const { return P(-y, x); } // rotates +90 degrees
P normal() const { return perp().unit(); }
// returns point rotated ’a ’ radians ccw around the origin
P rotate(double a) const {
return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
friend ostream& operator<<(ostream& os, P p) {
return os << "(" << p.x << "," << p.y << ")"; }
};

typedef Point<double> P;
int main() {
	cin.tie(0)->sync_with_stdio(0);
    
    int pts;cin>>pts;
    if (pts==1){
        cout << "possible" << endl;
        return 0;
    }
    double perc;cin>>perc;
    int goal = ceil((double)pts*perc/100);
    vector<P> points(pts);
    rep(i,0,pts){
        double a,b;cin>>a>>b;
        points[i]=P(a,b);
    }

    for (int i=0;i<1'000;i++){
        int rand_a=rand()%pts;
        int rand_b=rand()%pts;
        while (rand_a==rand_b)rand_b=rand()%pts;
        P a = points[rand_a];
        P b = points[rand_b];
        int cnt=0;
        for (auto l:points){
            if (a.cross(b,l)==0)cnt++;
        }
        if (cnt>=goal){
            cout << "possible" << endl;
            return 0;
        }
    }
    cout << "impossible" << endl;


}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
55
0 0
10 10
10 0
0 10
3 3

output:

possible

result:

ok single line: 'possible'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3748kb

input:

5
45
0 0
10 10
10 0
0 10
3 4

output:

impossible

result:

ok single line: 'impossible'

Test #3:

score: 0
Accepted
time: 401ms
memory: 4736kb

input:

100000
50
947055121 839845809
456002579 462331427
520074167 511588775
260741631 312217519
558282470 383028116
282546205 328980573
578265862 400696052
513864159 506814607
880696095 668083991
803833719 600127583
887503454 674102588
655824499 615951747
896115271 800683959
857382667 647471867
569870141 ...

output:

impossible

result:

ok single line: 'impossible'

Test #4:

score: 0
Accepted
time: 25ms
memory: 4808kb

input:

100000
50
810560889 734910937
363190213 772946635
130327202 286903706
391354640 831732788
292529496 625460172
399572437 848885371
86819798 196092950
760000601 696040889
979699529 864942377
689368161 641739649
159435693 347660355
547273227 532499035
197843870 427827758
294108151 628755217
629096345 5...

output:

possible

result:

ok single line: 'possible'

Test #5:

score: 0
Accepted
time: 26ms
memory: 4816kb

input:

100000
50
820054091 742209179
957209529 847652377
126690261 279312507
743801919 683587567
218048866 470000602
277558572 594212136
70714984 162478204
346353103 378034431
355811705 385306073
463418743 468032871
451830462 957960846
72543661 166295107
330323793 704346255
67673745 156130383
146278993 320...

output:

possible

result:

ok single line: 'possible'

Test #6:

score: 0
Accepted
time: 127ms
memory: 4892kb

input:

100000
20
703292684 530194841
809885530 655508862
886452530 663578368
222455004 151484174
960881347 763346432
620833000 392218447
40967275 83169944
387214516 143258043
27345864 32925413
137997945 373475948
112225041 532459761
26663473 476978006
222071077 762582542
306900661 528021622
75166559 246818...

output:

impossible

result:

ok single line: 'impossible'

Test #7:

score: 0
Accepted
time: 13ms
memory: 3692kb

input:

10000
20
703292684 530194841
809885530 655508862
886452530 663578368
222455004 151484174
960881347 763346432
620833000 392218447
40967275 83169944
387214516 143258043
27345864 32925413
137997945 373475948
112225041 532459761
26663473 476978006
222071077 762582542
306900661 528021622
75166559 2468186...

output:

impossible

result:

ok single line: 'impossible'

Test #8:

score: 0
Accepted
time: 2ms
memory: 3964kb

input:

1000
20
703292684 530194841
809885530 655508862
886452530 663578368
222455004 151484174
960881347 763346432
620833000 392218447
40967275 83169944
387214516 143258043
27345864 32925413
137997945 373475948
112225041 532459761
26663473 476978006
222071077 762582542
306900661 528021622
75166559 24681868...

output:

impossible

result:

ok single line: 'impossible'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

10
20
703292684 530194841
809885530 655508862
886452530 663578368
222455004 151484174
960881347 763346432
620833000 392218447
40967275 83169944
387214516 143258043
27345864 32925413
137997945 373475948

output:

possible

result:

ok single line: 'possible'

Test #10:

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

input:

100
20
1 99
73 76
84 86
91 31
71 58
39 7
70 1
20 47
35 19
51 67
13 94
79 52
65 31
52 86
58 37
76 26
35 15
68 86
0 58
16 38
83 21
11 52
90 31
65 24
51 82
58 30
75 36
82 5
67 100
91 91
36 33
83 37
14 51
22 81
75 5
18 57
26 30
75 15
27 39
6 78
20 64
74 61
100 55
66 32
54 23
89 56
56 38
94 70
55 15
50 2...

output:

impossible

result:

ok single line: 'impossible'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3740kb

input:

20
20
1 99
73 76
84 86
91 31
71 58
39 7
70 1
20 47
35 19
51 67
13 94
79 52
65 31
52 86
58 37
76 26
35 15
68 86
0 58
16 38

output:

impossible

result:

ok single line: 'impossible'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3748kb

input:

10
20
1 99
73 76
84 86
91 31
71 58
39 7
70 1
20 47
35 19
51 67

output:

possible

result:

ok single line: 'possible'

Test #13:

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

input:

1000
50
449069564 589649758
331791165 715891374
518893222 744025891
290211365 633528699
409411157 869643681
451121917 952265766
535238210 780163729
278228525 609792684
567297376 851044720
595024980 912348874
626229048 981339292
465961254 626996323
461664197 973148271
265381349 584344563
430285444 54...

output:

possible

result:

ok single line: 'possible'

Test #14:

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

input:

1000
50
179189561 653237294
775285118 853378017
117110895 435040133
96185449 361490342
697164870 718124769
258945727 933568205
157146897 575760650
674418482 678742881
273823111 985859969
220045799 796840817
183479301 668315084
735810519 785033793
134844963 497372711
236393951 854302109
704575683 730...

output:

possible

result:

ok single line: 'possible'

Test #15:

score: 0
Accepted
time: 42ms
memory: 4820kb

input:

100000
20
546774887 320050996
453141557 288652150
383672380 697261046
793906164 873824281
614905774 744778196
695930474 851208946
639385014 701643571
829876027 414985664
925618072 447091643
362080154 412676746
673514067 530834821
573486594 690371646
325927314 365187846
382722886 695084053
641867564 ...

output:

possible

result:

ok single line: 'possible'

Test #16:

score: 0
Accepted
time: 25ms
memory: 4736kb

input:

100000
20
322500359 930806243
903809730 525240737
695997043 254295597
699751395 596445820
958554970 954706557
728624015 262251435
769429451 272201529
896036197 779317082
267463463 830470883
905830844 884058135
499207872 286755902
698823588 404415572
901114307 877738146
307939185 904260403
745984575 ...

output:

possible

result:

ok single line: 'possible'

Test #17:

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

input:

100000
20
879000644 875670274
882276132 498856666
735718694 722598874
592868697 633665850
852772398 845869636
954859014 956711514
972131031 417842130
942437198 561470651
956638082 576250541
879395775 357721392
677324940 629267836
872257719 353093754
974629410 594975421
909546452 527238866
669519294 ...

output:

possible

result:

ok single line: 'possible'

Test #18:

score: 0
Accepted
time: 25ms
memory: 4820kb

input:

100000
20
331673984 971305815
357206895 452378730
783183076 537839830
915298493 481699441
999875620 646186102
987703553 522539149
322988684 946708515
396258328 516785060
324532912 951081863
897181335 421416672
601141477 854692550
872357748 582427166
843466148 441182770
478814457 652942350
913002852 ...

output:

possible

result:

ok single line: 'possible'

Test #19:

score: 0
Accepted
time: 32ms
memory: 4768kb

input:

100000
20
688376801 631676322
509555517 779389866
786385486 757206930
524631554 750882600
859415386 177892761
494317486 456720930
598264232 823467126
430099234 390651776
951129527 953598555
632937077 563752080
734760233 688504878
707385524 931035090
986072729 996410646
728503118 141103547
666924906 ...

output:

possible

result:

ok single line: 'possible'

Test #20:

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

input:

100000
20
630900138 992088704
392986220 731446795
358952516 224861773
524220380 178643539
410460376 788537017
905048076 550888973
949441070 577392253
665247084 637932076
532406952 771144530
657175332 630336098
458830176 946567117
539197668 519312402
717870420 687453630
542708529 794253473
875718290 ...

output:

possible

result:

ok single line: 'possible'

Test #21:

score: 0
Accepted
time: 180ms
memory: 4796kb

input:

100000
20
197365433 995249912
273784820 567447356
881399484 136163532
286229835 600935760
434426840 999720428
593060698 315405484
196428945 990233012
729360701 406713253
189779785 954612512
381187728 61227840
336516641 143545873
796808060 783768097
195928753 987553412
233805045 459865416
894523040 8...

output:

impossible

result:

ok single line: 'impossible'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3688kb

input:

15
20
403949330 352508333
710241605 536518104
869308273 743024188
968701422 912883315
700690932 553057042
965958569 329762264
914069436 748952324
691814931 701922179
645060602 477583364
718002655 29698893
907202332 485913059
2427733 11105326
752912982 748473075
457647582 958089608
692028967 95601809

output:

possible

result:

ok single line: 'possible'

Test #23:

score: 0
Accepted
time: 0ms
memory: 3744kb

input:

15
20
761919890 158960745
627007356 675611814
687629565 574094719
486782045 815710133
974592631 963133993
887677162 258371325
122413585 728693559
684159262 76383007
329083211 182102887
475763461 108416814
111846843 497477627
492556149 820659365
402204012 927482004
615420008 533311320
676102897 97798...

output:

possible

result:

ok single line: 'possible'

Test #24:

score: 0
Accepted
time: 0ms
memory: 3740kb

input:

15
20
46482907 503652795
617212435 881739482
836055420 238931512
742485407 339788284
314886165 128393590
637453276 473625792
658484821 482038410
324497775 583444634
835330451 552776662
518594349 893677556
197013435 274144505
254686901 216447336
761659159 166798872
29882077 225364499
797883698 898988...

output:

possible

result:

ok single line: 'possible'

Test #25:

score: 0
Accepted
time: 0ms
memory: 3748kb

input:

15
20
347513467 724723849
341832699 973370691
311144631 601834206
728563139 742339817
53546988 398179733
710258650 663507833
89525181 199819534
100423498 829362804
103638890 871162900
39856714 901237847
123727769 748610445
7464499 108313659
87000730 654866820
488410331 423715088
508750067 308647564

output:

possible

result:

ok single line: 'possible'

Test #26:

score: 0
Accepted
time: 0ms
memory: 3692kb

input:

15
20
653875792 582098654
758344763 984955724
977916427 525955627
543242963 514539197
105483332 206526572
971084752 958784294
430936973 487614831
31233766 83389316
104477281 950172971
627616283 684768650
58390042 873783494
112432268 670656226
581275024 495885242
589687112 760546038
279973417 401322238

output:

possible

result:

ok single line: 'possible'

Test #27:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

15
20
468912313 743344011
108634382 658643875
348239125 454081557
21684280 126233521
609596243 954369906
45180168 594463463
930486011 396527202
153235954 147466176
401635737 86300493
427365698 413382121
503472353 609131881
696276356 531867324
785459453 683299087
700039541 355594258
602568313 943828011

output:

possible

result:

ok single line: 'possible'

Test #28:

score: 0
Accepted
time: 0ms
memory: 3684kb

input:

15
20
52827742 724294718
75825449 534378573
560249308 886001217
642275261 259239851
747604196 88320278
757119968 501528444
58790428 370026954
111026245 852414240
351142233 744641549
526203398 362978502
664756018 446110074
195893733 781665577
649340939 25458155
935503371 53861934
644663741 780887866

output:

possible

result:

ok single line: 'possible'

Test #29:

score: 0
Accepted
time: 0ms
memory: 3744kb

input:

15
20
175013431 313218655
801465866 240927346
33653765 268755300
352660142 394242935
574167257 731252441
541820028 459337620
993777548 993038139
137720800 68830854
999817362 877649783
202730506 310997642
873019567 941082404
830917549 56947732
591336251 671731604
562481083 459043707
632804394 591678516

output:

possible

result:

ok single line: 'possible'

Test #30:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

15
20
107731538 381911051
792436109 863228551
299169867 68491525
223355668 999452937
924303618 175539562
758072201 803091712
774168473 831260188
595062813 966455826
257167005 101779880
933024396 786817162
329887675 947413557
863808896 134135559
110141532 328482328
40574042 331503431
662090958 409474...

output:

possible

result:

ok single line: 'possible'

Test #31:

score: 0
Accepted
time: 0ms
memory: 3740kb

input:

15
20
610381560 578332670
636282320 756642952
260144657 60750461
63912480 724518826
375939560 414181414
432435231 399290998
393242101 786929001
81040288 242415434
220883964 960186064
895379588 185348224
967134192 455615063
575013539 645636018
701274814 790890189
182600685 339315992
214301717 406680685

output:

possible

result:

ok single line: 'possible'

Test #32:

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

input:

1000
30
978381577 747234790
904655197 684040750
245082331 743796196
934757409 709842646
961292435 732586954
930928699 143093718
947290139 720584986
968206069 147872868
913345221 691489342
874354437 658068670
923165045 699906334
753131092 120299153
283410743 820453020
147298515 548228564
277766581 80...

output:

possible

result:

ok single line: 'possible'

Test #33:

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

input:

1000
31
704177159 757825154
837556499 354067558
727090364 314413048
224110796 133856280
22996441 577090909
582144719 262381278
739656464 982714638
626663445 792410606
515737157 238542666
565135156 688784014
852755527 985062658
844503647 356561406
744485729 320657538
674951622 873738062
287195792 156...

output:

possible

result:

ok single line: 'possible'

Test #34:

score: 0
Accepted
time: 0ms
memory: 3764kb

input:

1000
32
326453804 215589623
731266119 767608085
310983928 203376563
748302089 787333945
633931019 654904285
806542878 594607313
880887775 940854213
160771393 297060689
443684569 980767531
678008999 493133198
398069440 272128283
456789415 318486158
698465520 509283083
186767869 359885506
396747179 38...

output:

possible

result:

ok single line: 'possible'

Test #35:

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

input:

1000
33
575479072 694187549
966419392 418516151
494923444 600205983
743130586 889780982
810344126 275951236
712410173 245817712
693447200 299090817
642378310 772236660
469622194 570687858
962666880 416874427
667311899 231941320
681579296 293898609
922528480 399313877
721204054 864200028
753641246 25...

output:

possible

result:

ok single line: 'possible'

Test #36:

score: 0
Accepted
time: 2ms
memory: 3760kb

input:

1000
34
754786163 782593542
212573013 781706899
257379126 910557588
271163077 961984019
216893238 794999899
811987811 821919675
150923412 592015819
245210486 877370388
225954722 824854668
189408027 710430019
700893155 745542099
260789610 919858908
716468163 756249917
276868894 979540379
185984035 69...

output:

impossible

result:

ok single line: 'impossible'

Test #37:

score: 0
Accepted
time: 2ms
memory: 3960kb

input:

1000
35
360769421 721082060
340959581 674859100
205725005 673403634
156409607 533676673
864540267 819811537
407466641 830042240
955867959 873086024
472399136 981551395
376237796 757174935
479723139 832931531
899646831 840290366
296897291 931725111
200627729 658961352
376746191 758361190
389795216 78...

output:

impossible

result:

ok single line: 'impossible'

Test #38:

score: 0
Accepted
time: 0ms
memory: 3768kb

input:

1000
36
699958906 263213606
824226946 337774430
873113186 367106174
292048392 342503611
543970932 657406786
815475588 996787606
946185166 410949362
777731052 949606936
114952293 677380569
104880008 625004687
498976488 601163731
468996852 563689186
124618243 727643509
982878566 432965402
655887526 23...

output:

impossible

result:

ok single line: 'impossible'

Test #39:

score: 0
Accepted
time: 2ms
memory: 3704kb

input:

1000
37
224388936 733732582
283179896 998291902
650142787 526837275
238207560 795916390
188360599 142018785
592071781 478444770
848997435 900489525
621258345 627202617
759133005 792652209
186247696 562097002
258323752 886439254
207277936 656733082
829200125 876732753
170571192 491552734
902586727 73...

output:

impossible

result:

ok single line: 'impossible'

Test #40:

score: 0
Accepted
time: 2ms
memory: 3760kb

input:

1000
38
308465475 336807233
826467255 747707625
948115265 819590540
878136543 778239477
859657160 802837537
832898141 751507694
810143101 738061534
591031684 467055692
646902520 536894237
281007031 298787849
280281501 297783269
805318611 735210699
520652047 630604025
381147279 437443577
699398901 87...

output:

impossible

result:

ok single line: 'impossible'

Test #41:

score: 0
Accepted
time: 2ms
memory: 3708kb

input:

1000
39
981702454 847756919
831474249 923011761
749171174 663335559
879950299 957637511
858626245 958789648
826577241 925507990
934557705 810366256
799745489 900348361
912996907 981242231
805344215 904347451
599296187 689485357
860419491 960651865
831306047 728477010
568798213 657814384
759591109 87...

output:

impossible

result:

ok single line: 'impossible'

Test #42:

score: 0
Accepted
time: 180ms
memory: 4892kb

input:

100000
20
999992222 388915560
999988046 597723909
999991734 413316535
999999901 4950200
999997622 118904758
999989488 525621026
999993938 303112128
999992382 380915236
999984281 785981438
999993591 320462822
999992279 386065446
999998590 70502823
999982679 866084645
999998625 68752754
999988661 5669...

output:

impossible

result:

ok single line: 'impossible'

Test #43:

score: 0
Accepted
time: 183ms
memory: 4828kb

input:

100000
20
912536502 999981750
120304815 999997594
911836473 999981764
876935079 999982462
4500180 999999910
118954759 999997621
35751430 999999285
305312212 999993894
423566942 999991529
919436777 999981612
125255012 999997495
492769713 999990145
226809074 999995464
991689667 999980167
55702232 9999...

output:

impossible

result:

ok single line: 'impossible'

Test #44:

score: 0
Accepted
time: 25ms
memory: 4832kb

input:

100000
20
999999048 47601908
999980023 998889958
999992000 400016002
999988053 597373897
999982012 899435977
999990740 463018523
999982578 871134848
999985892 705428220
999998336 83203332
999999698 15100605
999984288 785631424
999992629 368564746
999985623 718878754
999987692 615424620
999980343 982...

output:

possible

result:

ok single line: 'possible'

Test #45:

score: 0
Accepted
time: 26ms
memory: 4688kb

input:

100000
20
142305692 999997154
421316855 999991574
97553905 999998049
412016484 999991760
220858836 999995583
791031641 999984180
196457862 999996071
698127928 999986038
936737470 999981266
222558905 999995549
942337694 999981154
203808155 999995924
95553823 999998089
362114485 999992758
697627908 99...

output:

possible

result:

ok single line: 'possible'

Test #46:

score: 0
Accepted
time: 19ms
memory: 4208kb

input:

65536
20
0 1000000000
405769948 610048249
132971348 701460537
402500935 156291477
44622295 841273224
185 999999785
413448866 875064609
252239757 821088177
584203807 253422497
379074700 251769352
370 999999570
226944406 952042903
140459605 958895128
689886692 251558658
611195902 843518673
555 9999993...

output:

possible

result:

ok single line: 'possible'

Test #47:

score: 0
Accepted
time: 28ms
memory: 4844kb

input:

100000
23
999965479 34521
999965456 34572
999965433 34623
999965410 34674
999965387 34725
999965364 34776
999965341 34827
999965318 34878
999965295 34929
999965272 34980
999965249 35031
999965226 35082
999965203 35133
999965180 35184
999965157 35235
999965134 35286
999965111 35337
999965088 35388
99...

output:

possible

result:

ok single line: 'possible'

Test #48:

score: 0
Accepted
time: 25ms
memory: 4836kb

input:

100000
22
42582253 8664389
516375629 868112088
294356706 31985904
177424449 181299826
864230006 60212986
972082427 950529831
823807977 920063363
226730421 171028557
248786379 678161177
932323525 815231868
29683489 602673151
31127180 593952590
116207869 7507636
911326775 174501465
763307459 390014663...

output:

possible

result:

ok single line: 'possible'

Test #49:

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

input:

100000
24
924001091 773134790
50210213 438623483
761766184 809830442
729207936 23073002
37448065 708098155
236248281 887550927
849864281 771642302
127902399 215047221
876031002 128369823
116319068 142073158
592257977 815034766
808015992 10406962
975351127 554079371
307061921 674666856
408495540 6355...

output:

possible

result:

ok single line: 'possible'

Test #50:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

1
100
167 1234

output:

possible

result:

ok single line: 'possible'

Test #51:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

1
20
167 1234

output:

possible

result:

ok single line: 'possible'

Test #52:

score: 0
Accepted
time: 0ms
memory: 3716kb

input:

2
20
167 1234
83712641 16528341

output:

possible

result:

ok single line: 'possible'

Test #53:

score: 0
Accepted
time: 0ms
memory: 3744kb

input:

2
100
167 1234
83712641 16528341

output:

possible

result:

ok single line: 'possible'

Test #54:

score: 0
Accepted
time: 0ms
memory: 3944kb

input:

3
67
123412 1234621
42611 12345
365258 23511

output:

impossible

result:

ok single line: 'impossible'

Test #55:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

3
66
123412 1234621
42611 12345
365258 23511

output:

possible

result:

ok single line: 'possible'

Test #56:

score: 0
Accepted
time: 0ms
memory: 3716kb

input:

3
67
1234 1234
1238 1246
1246 1270

output:

possible

result:

ok single line: 'possible'

Test #57:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

5
100
45 7
2341 7
962 7
5927859 7
93825 7

output:

possible

result:

ok single line: 'possible'

Test #58:

score: 0
Accepted
time: 0ms
memory: 3752kb

input:

5
76
741295 827354
741295 10487234
741295 59275
741295 652
741295 4873

output:

possible

result:

ok single line: 'possible'

Test #59:

score: 0
Accepted
time: 0ms
memory: 3680kb

input:

5
60
234123 5123451
3858123 5123451
234123 93817723
28104 5123451
234123 0

output:

possible

result:

ok single line: 'possible'

Test #60:

score: 0
Accepted
time: 0ms
memory: 3688kb

input:

10
20
0 0
1 1
2 3
3 6
4 10
5 15
6 21
7 28
8 36
9 45

output:

possible

result:

ok single line: 'possible'

Test #61:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

15
20
0 0
1 1
2 3
3 6
4 10
5 15
6 21
7 28
8 36
9 45
10 55
11 66
12 78
13 91
14 104

output:

possible

result:

ok single line: 'possible'

Test #62:

score: 0
Accepted
time: 0ms
memory: 3744kb

input:

11
27
0 0
1 0
3 1
4 1
13 3
14 3
42 4
43 4
99 5
100 5
999999997 2

output:

impossible

result:

ok single line: 'impossible'

Test #63:

score: 0
Accepted
time: 0ms
memory: 3748kb

input:

11
27
0 0
0 1
1 3
1 4
3 13
3 14
4 42
4 43
5 99
5 100
2 999999997

output:

impossible

result:

ok single line: 'impossible'