QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#389655#8550. All the Way Leftucup-team1198AC ✓2283ms174752kbC++144.1kb2024-04-14 17:35:192024-04-14 17:35:19

Judging History

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

  • [2024-04-14 17:35:19]
  • 评测
  • 测评结果:AC
  • 用时:2283ms
  • 内存:174752kb
  • [2024-04-14 17:35:19]
  • 提交

answer

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

mt19937_64 rnd;

struct Vector {
    int x;
    int y;

    Vector(int x = 0, int y = 0): x(x), y(y) {}
    Vector(const Vector& u, const Vector& v): x(v.x - u.x), y(v.y - u.y) {}

    int sqlen() const { return x * x + y * y; }
};

Vector operator-(const Vector& a, const Vector& b) {
    return Vector(b, a);
}

int operator%(const Vector& a, const Vector& b) {
    return a.x * b.y - a.y * b.x;
}

bool hp(const Vector& v) {
    if (v.y == 0) return v.x > 0;
    return v.y > 0;
}

bool operator<(const Vector& u, const Vector& v) {
    if (hp(u) == hp(v)) {
        return u % v > 0;
    }
    return hp(u);
}

istream& operator>>(istream& in, Vector& v) {
    in >> v.x >> v.y;
    return in;
}

void solve() {
    int n;
    cin >> n;
    vector<Vector> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    if (n == 1) {
        cout << "1\n";
        return;
    }

    vector<Vector> hull;
    int sz = 0;
    vector<Vector> cent;
    Vector min_p = a[0];
    for (int i = 1; i < n; ++i) {
        if (a[i].x < min_p.x) {
            min_p = a[i];
        } else if (a[i].x == min_p.x && a[i].y < min_p.y) {
            min_p = a[i];
        }
    }
    for (int i = 0; i < n; ++i) {
        a[i] = a[i] - min_p;
    }

    sort(a.begin(), a.end(), [](Vector u, Vector v){
        if (u % v == 0) {
            return u.sqlen() < v.sqlen();
        }
        return u % v > 0;
    });

    Vector rgh = a.back();
    sort(a.begin() + 1, a.end(), [&rgh](Vector u, Vector v) {
        if (u % v == 0) {
            if (rgh % u == 0) {
                return u.sqlen() > v.sqlen();
            }
            return u.sqlen() < v.sqlen();
        }
        return u % v > 0;
    });

    for (Vector p : a) {
        /// cerr << p.x << " " << p.y << endl;
        while (sz >= 2 && (hull[sz - 1] - hull[sz - 2]) % (p - hull[sz - 1]) < 0) {
            cent.push_back(hull.back());
            hull.pop_back();
            --sz;
        }
        hull.push_back(p);
        ++sz;
    }

    bool is_line = true;
    for (int i = 2; i < sz; ++i) {
        if ((hull[i] - hull[0]) % (hull[i] - hull[1]) != 0) {
            is_line = false;
            break;
        }
    }
    if (is_line) {
        cout << "2\n";
        return;
    }
    int ans = hull.size(); /// left part is empty;
    vector<int> hsh(n);
    for (int i = 0; i < n; ++i) {
        hsh[i] = rnd();
    }
    unordered_set<int> opt;
    for (int i = 0; i < (int)cent.size(); ++i) {
        int cur = hsh[i];
        int ind = -1;
        vector<pair<Vector, int>> ev;
        for (int j = 0; j < (int)cent.size(); ++j) {
            if (i == j) continue;
            ev.push_back({cent[j] - cent[i], j});
            ev.push_back({cent[i] - cent[j], j});
        }
        for (int j = 0; j < sz; ++j) {
            ev.push_back({hull[j] - cent[i], j + cent.size()});
        }
        for (int j = 0; j < (int)cent.size(); ++j) {
            if (i == j) continue;
            if (hp(cent[j] - cent[i])) {
                cur ^= hsh[j];
            }
        }
        for (int j = 0; j < sz; ++j) {
            if (!hp(hull[j] - cent[i]) && hp(hull[(j + 1) % sz] - cent[i])) {
                ind = j;
            }
        }
        sort(ev.begin(), ev.end());

        auto operate = [&](int i) {
            if (i >= cent.size()) {
                ind = i - cent.size();
            } else {
                cur ^= hsh[i];
            }
        };

        for (int j = 0; j < (int)ev.size(); ++j) {
            operate(ev[j].second);
            while (j + 1 < (int)ev.size() && ev[j].first % ev[j + 1].first == 0) {
                ++j;
                operate(ev[j].second);
            }
            opt.insert(cur ^ hsh[cent.size() + ind]);
        }
    }
    ans += opt.size();
    cout << ans << "\n";
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int tst;
    cin >> tst;
    while (tst--) solve();

    return 0;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

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

input:

3
4
1 1
3 1
2 2
2 3
3
1 1
1 2
1 3
6
1 1
2 1
2 2
2 3
3 2
4 2

output:

6
2
13

result:

ok 3 number(s): "6 2 13"

Test #2:

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

input:

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

output:

1
2
2
3
8
14
12
16
22
10
54
32
28
10
14

result:

ok 15 numbers

Test #3:

score: 0
Accepted
time: 10ms
memory: 3652kb

input:

10000
7
999999994 1000000000
999999998 999999997
999999999 999999994
999999998 999999994
999999996 999999998
1000000000 999999994
1000000000 999999997
6
999999998 5
999999998 6
999999994 5
999999994 1
999999998 4
999999995 5
7
2 2
3 6
7 5
3 5
2 4
7 4
6 2
3
77279810 642022026
309119240 107003671
4636...

output:

17
10
12
3
2
4
2
21
5
12
2
1
4
3
17
1
3
16
2
5
10
1
4
1
4
8
1
17
4
12
2
2
16
3
4
6
3
17
2
5
2
3
4
21
5
4
6
4
17
2
10
12
2
10
5
4
1
1
4
2
8
15
5
10
10
4
12
2
4
2
12
1
4
1
10
1
4
14
2
2
5
8
1
17
1
3
8
2
2
16
13
4
10
2
12
12
1
2
21
2
5
8
3
12
2
17
3
4
17
10
1
12
1
5
8
8
10
1
8
8
4
3
4
5
12
5
1
1
4
2
2
...

result:

ok 10000 numbers

Test #4:

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

input:

10000
10
1000000000 999999996
999999992 999999996
999999993 1000000000
999999996 999999998
999999992 999999991
999999996 999999999
999999993 999999993
999999991 999999995
999999995 999999997
999999998 999999997
9
999999995 1000000000
999999993 999999992
999999999 1000000000
999999998 999999999
99999...

output:

47
16
29
34
28
14
36
26
14
26
15
34
8
16
32
38
2
44
3
19
14
4
6
33
10
10
12
12
17
8
25
8
33
14
30
11
10
19
40
34
33
41
6
5
22
10
17
16
6
16
2
41
29
33
20
26
10
21
2
32
26
47
33
3
31
12
30
16
14
24
10
12
22
17
40
6
23
26
23
17
28
3
16
4
36
46
12
3
48
21
6
14
39
40
29
23
33
34
12
9
6
10
12
32
34
3
28
...

result:

ok 10000 numbers

Test #5:

score: 0
Accepted
time: 330ms
memory: 3908kb

input:

10000
20
10 472423976
2 859313061
15 542767446
2 894484796
7 577939181
2 577939181
10 929656531
4 683454386
8 507595711
1 788969591
15 718626121
15 964828266
1 507595711
4 964828266
3 507595711
15 472423976
12 718626121
15 648282651
8 648282651
11 753797856
20
19 999999999
12 999999995
8 999999996
2...

output:

195
197
238
225
192
211
234
249
242
211
225
261
240
230
209
209
183
214
183
225
240
242
141
241
191
245
170
232
259
191
194
242
222
229
189
210
216
250
234
202
225
243
185
195
237
249
240
176
172
211
203
232
203
209
235
212
218
246
199
196
223
210
207
230
211
178
204
227
245
228
191
190
187
226
206
...

result:

ok 10000 numbers

Test #6:

score: 0
Accepted
time: 328ms
memory: 3604kb

input:

10000
20
999999990 999999987
999999993 999999991
999999991 999999996
999999997 999999991
999999997 999999999
999999986 999999990
999999989 999999993
999999988 999999992
999999986 999999998
999999993 999999989
1000000000 999999994
999999995 999999988
999999991 999999989
999999994 999999994
999999996 ...

output:

250
208
219
215
216
224
160
224
185
209
186
231
205
210
209
248
189
198
224
233
221
232
216
213
221
230
203
213
208
242
201
227
254
210
206
246
239
246
172
213
223
205
218
232
194
228
230
208
247
209
238
245
224
251
234
214
221
256
231
245
240
228
158
213
242
231
192
232
221
208
190
232
208
247
229
...

result:

ok 10000 numbers

Test #7:

score: 0
Accepted
time: 1629ms
memory: 86516kb

input:

6
423
871052589 696370203
590606822 96125207
424963175 275218135
401552023 62808380
458556639 213160485
955603590 401616993
117520530 336079323
391036678 62821894
739838559 290358804
850343513 195705313
352952487 42119649
437338877 866366388
803885262 795778899
279023855 479705056
213974465 14674106...

output:

114514
1919810
1199282
974
26
1

result:

ok 6 numbers

Test #8:

score: 0
Accepted
time: 661ms
memory: 15276kb

input:

16
486
34060622 598468879
128647540 757780661
668466425 88271354
261524546 867470097
778177586 166231958
47339886 371835886
360942672 75140367
653090531 80941869
576631367 900830133
222375990 156853949
720877739 828175248
338270557 85134793
108934265 736556394
895297321 597692835
347786961 901398783...

output:

486
7442
6974
6402
113282
112138
121422
129176
272936
246268
273992
219769
265227
271284
229925
240937

result:

ok 16 numbers

Test #9:

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

input:

1
2000
368963 449991602
71690645 226469653
116119489 746924303
14456657 563523216
591696265 879438989
116209515 163496764
836456898 655094478
241619408 855832580
408694125 7058835
858105702 606589269
461893647 907489045
881686694 476771541
10299543 372869886
546580179 23973978
139944331 772781268
28...

output:

2000

result:

ok 1 number(s): "2000"

Test #10:

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

input:

1
2000
744286402 946400742
987763934 558344530
230642709 255584833
988354826 529569285
613631408 79006321
909007166 283642901
871800686 234872909
146697513 660667263
535381193 990122896
433983054 96440320
935182589 327092675
295229766 874996034
943116516 729567432
841158498 871565488
955381041 69966...

output:

29972

result:

ok 1 number(s): "29972"

Test #11:

score: 0
Accepted
time: 4ms
memory: 4636kb

input:

1
2000
769001450 754042265
25824918 578315923
195176522 830526044
660198770 102506141
176341551 814219275
361352592 56309147
860529759 319890700
143425404 781406087
826853273 258071284
452236374 42034217
857754231 612265458
870615679 346554880
366416325 54982850
132539126 199271969
320819767 6934938...

output:

29971

result:

ok 1 number(s): "29971"

Test #12:

score: 0
Accepted
time: 6ms
memory: 5184kb

input:

1
2000
92720650 320701832
868133136 724198785
701884285 873543357
132356020 684571482
523287572 31342492
396060735 44855451
949796867 494382726
833231382 768226875
943663059 423388738
896856813 680016197
505995366 30299910
520044988 913510433
254035248 816180553
586865276 42481991
156803847 21672662...

output:

39952

result:

ok 1 number(s): "39952"

Test #13:

score: 0
Accepted
time: 862ms
memory: 89032kb

input:

1
2000
921789228 394167112
67185499 569719790
684705345 738829782
360866636 555114318
846959948 713988184
113410674 337530338
935834181 437688129
251894406 879810056
97433362 685968840
899809289 344067418
832269999 246885813
381274629 252518169
826624109 240601626
495034793 888656585
313389757 52178...

output:

2007992

result:

ok 1 number(s): "2007992"

Test #14:

score: 0
Accepted
time: 863ms
memory: 88620kb

input:

1
2000
968352104 382682494
169810362 227039536
717966561 160707606
441686790 182476923
960722652 351321012
194467730 375514261
365912762 393135748
68576498 440778225
200672368 240077910
397172893 114006499
233424163 565208946
841069449 748138623
564685706 288340610
716483745 416169983
512789522 2061...

output:

1991245

result:

ok 1 number(s): "1991245"

Test #15:

score: 0
Accepted
time: 835ms
memory: 88600kb

input:

1
2000
339176530 362568555
954193274 419874680
511252289 988095198
90577325 572931848
521801976 138222296
235718442 856540834
689641989 940798368
163398420 342947025
908225644 338858057
931756216 559295464
596071112 194491827
892126869 413782835
334449675 192351238
199298090 299769065
957948062 6450...

output:

1992324

result:

ok 1 number(s): "1992324"

Test #16:

score: 0
Accepted
time: 862ms
memory: 88252kb

input:

1
2000
68023959 545355429
670976741 740016128
756274710 590394389
95885493 595690247
871395167 275123465
98557357 323741788
173795686 765626033
636750940 898363001
369796607 443301889
85748860 596231201
609909361 502550923
168226277 758782771
924672923 384159791
944148082 531941372
111732960 6502023...

output:

1984618

result:

ok 1 number(s): "1984618"

Test #17:

score: 0
Accepted
time: 2182ms
memory: 174108kb

input:

1
2000
472317399 448095139
470057957 630422151
640572269 820742041
486621970 364956001
331756721 458127349
562088574 699893181
484360656 420118046
632196877 918382826
269387963 389598905
547430457 816036894
694837907 511061315
696696481 622416483
280660508 154457223
537659096 840781651
563474056 473...

output:

3974024

result:

ok 1 number(s): "3974024"

Test #18:

score: 0
Accepted
time: 2172ms
memory: 173904kb

input:

1
2000
129892852 719880988
184919537 744105353
587102697 605473274
626545113 393257114
31249917 443389504
380359906 519791025
15047745 453844828
219382764 706338434
420710714 93495564
498185131 959746121
539399219 546379388
468794808 287432388
269897958 886528743
481025128 602157701
469331767 410256...

output:

3961204

result:

ok 1 number(s): "3961204"

Test #19:

score: 0
Accepted
time: 2179ms
memory: 173944kb

input:

1
2000
510934899 547459563
519773921 365901465
496833202 515167890
654302266 231507260
733500503 460686130
432606988 77262088
25742008 636637521
134014773 686685517
379041620 252939972
681864072 251338397
855737338 246632327
309623668 229200708
692820865 277464076
288511703 248016522
286589348 51658...

output:

3964062

result:

ok 1 number(s): "3964062"

Test #20:

score: 0
Accepted
time: 2283ms
memory: 173432kb

input:

1
2000
576715016 547277070
523392466 802721752
291730288 525334491
250099054 367469786
579560721 503865147
501420548 121382497
171360657 415872990
799343254 503750072
855064541 339988698
213016439 769254586
688291370 403587977
730744033 763739908
455349062 271922867
388474585 366824606
395462272 579...

output:

3950522

result:

ok 1 number(s): "3950522"

Test #21:

score: 0
Accepted
time: 2265ms
memory: 174752kb

input:

1
2000
753399490 201420747
622181549 316348181
483137284 427471103
505501632 411398075
288945757 424009445
779719655 127660483
535994596 268390059
802466895 146833111
278458488 408398286
706788106 206012131
295405397 508692108
406905279 348331770
295353809 617182872
504337995 296574757
697746154 174...

output:

3992006

result:

ok 1 number(s): "3992006"

Test #22:

score: 0
Accepted
time: 2230ms
memory: 174716kb

input:

1
2000
592736101 387284482
296073032 334186116
297857412 337555925
571732208 422401938
537700347 361036768
717213209 359576899
604927787 419384975
428138181 430955572
755558311 368389007
319563812 359681733
581471767 439734361
513676681 306659848
240266587 292815356
598054066 420025744
186430824 263...

output:

3991252

result:

ok 1 number(s): "3991252"

Test #23:

score: 0
Accepted
time: 2207ms
memory: 174724kb

input:

1
2000
254482463 216326928
259688225 367860109
96889623 353950264
809227232 836951665
345354028 141005819
204570694 193377866
495650122 618254587
315571658 154789888
303782568 237636907
681975339 717893197
610887176 663410028
352777025 298763925
385694796 206052374
340672163 388607943
568842186 6266...

output:

3989972

result:

ok 1 number(s): "3989972"

Test #24:

score: 0
Accepted
time: 2216ms
memory: 174596kb

input:

1
2000
662922115 221115958
587015717 182861841
732973227 202525759
610031685 182122157
600636621 175085573
356522102 591899596
675852703 207364274
374792496 523848515
541017593 394706666
639387965 189373958
717822245 235655806
604403003 326462818
495811759 360263663
576264288 181772296
418013709 605...

output:

3983682

result:

ok 1 number(s): "3983682"

Extra Test:

score: 0
Extra Test Passed