QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #509926 | #8646. Card Collection | Max_s_xaM | 0 | 1ms | 5764kb | C++14 | 6.3kb | 2024-08-08 19:53:41 | 2024-08-08 19:53:42 |
answer
#include <iostream>
#include <algorithm>
#include <cstring>
typedef long long ll;
typedef double lf;
// #define DEBUG 1
struct IO
{
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
char buf[MAXSIZE], *p1, *p2;
char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
IO() : p1(buf), p2(buf), pp(pbuf) {}
~IO() {fwrite(pbuf, 1, pp - pbuf, stdout);}
#endif
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? ' ' : *p1++)
#define blank(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')
template <typename T>
void Read(T &x)
{
#if DEBUG
std::cin >> x;
#else
bool sign = 0; char ch = gc(); x = 0;
for (; !isdigit(ch); ch = gc())
if (ch == '-') sign = 1;
for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
if (sign) x = -x;
#endif
}
void Read(char *s)
{
#if DEBUG
std::cin >> s;
#else
char ch = gc();
for (; blank(ch); ch = gc());
for (; !blank(ch); ch = gc()) *s++ = ch;
*s = 0;
#endif
}
void Read(char &c) {for (c = gc(); blank(c); c = gc());}
void Push(const char &c)
{
#if DEBUG
putchar(c);
#else
if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
*pp++ = c;
#endif
}
template <typename T>
void Write(T x)
{
if (x < 0) x = -x, Push('-');
static T sta[35];
int top = 0;
do sta[top++] = x % 10, x /= 10; while (x);
while (top) Push(sta[--top] ^ 48);
}
template <typename T>
void Write(T x, char lst) {Write(x), Push(lst);}
} IO;
#define Read(x) IO.Read(x)
#define Write(x, y) IO.Write(x, y)
#define Put(x) IO.Push(x)
using namespace std;
const int MAXN = 2e5 + 10;
int n, m;
struct point
{
int x, y;
}a[MAXN];
int s, t;
int pre[9], suf[9];
int cx(int x) { return (x > s ? 2 : (x == s ? 1 : 0)); }
int cy(int y) { return (y > t ? 2 : (y == t ? 1 : 0)); }
int tr(int i) { return cx(a[i].x) * 3 + cy(a[i].y); }
int main()
{
// freopen("A.in", "r", stdin);
#if DEBUG
#else
ios::sync_with_stdio(0), cin.tie(0);
#endif
Read(n), Read(m);
for (int i = 1; i <= n; i++) Read(a[i].x), Read(a[i].y);
for (int _ = 1; _ <= m; _++)
{
Read(s), Read(t);
bool flag = 0;
int lp = 1; while (lp <= n && a[lp].x != s) lp++;
int rp = n; while (rp > 0 && a[rp].y != t) rp--;
if (lp <= rp)
{
memset(pre, 0, sizeof(pre)), memset(suf, 0, sizeof(suf));
int d0 = 0, d1 = 0, c0 = 0, c1 = 0;
bool a0[3] = {0}, a1[3] = {0};
for (int i = 1; i < lp; i++) tr(i) != tr(1) && !d0 && (d0 = i), pre[tr(i)] = i;
for (int i = n; i > rp; i--) tr(i) != tr(n) && !d1 && (d1 = i), suf[tr(i)] = i;
for (int i = 0; i < 9; i++) c0 += (bool)pre[i], c1 += (bool)suf[i];
if (lp == rp) { flag |= (c0 != 1 || (tr(1) != 2 && tr(1) != 6)) && (c1 != 1 || (tr(n) != 2 && tr(n) != 6)); goto NXT; }
if (cy(a[lp].y) == 1)
{
if (c0 != 1 || (tr(1) != 2 && tr(1) != 6)) a0[0] = a0[2] = 1;
else a0[3 - tr(1) / 2] = 1;
}
else
{
a0[cy(a[lp].y)] = c0 != 1 || !pre[cy(a[lp].y) * 2 + 2];
a0[2 - cy(a[lp].y)] = pre[cy(a[lp].y) * 2 + 2] && (pre[cy(a[lp].y) * 2 + 2] != d0 || tr(1) != 6 - 2 * cy(a[lp].y));
}
if (cx(a[rp].x) == 1)
{
if (c1 != 1 || (tr(n) != 2 && tr(n) != 6)) a1[0] = a1[2] = 1;
else a1[tr(n) / 2 - 1] = 1;
}
else
{
a1[cx(a[rp].x)] = c1 != 1 || !suf[6 - 2 * cx(a[rp].x)];
a1[2 - cx(a[rp].x)] = suf[6 - 2 * cx(a[rp].x)] && (suf[6 - 2 * cx(a[rp].x)] != d1 || tr(n) != cx(a[rp].x) * 2 + 2);
}
if ((a0[0] && a1[0]) || (a0[2] && a1[2])) { flag = 1; goto NXT; }
memset(pre, -1, sizeof(pre));
for (int i = lp + 1; i < rp; i++) pre[tr(i)] = 0;
flag |= !((pre[3] && pre[4] && pre[6] && pre[7]) || (pre[1] && pre[2] && pre[4] && pre[5]));
}
NXT:
lp = 1; while (lp <= n && a[lp].y != t) lp++;
rp = n; while (rp > 0 && a[rp].x != s) rp--;
if (lp <= rp)
{
memset(pre, 0, sizeof(pre)), memset(suf, 0, sizeof(suf));
int d0 = 0, d1 = 0, c0 = 0, c1 = 0;
bool a0[3] = {0}, a1[3] = {0};
for (int i = 1; i < lp; i++) tr(i) != tr(1) && !d0 && (d0 = i), pre[tr(i)] = i;
for (int i = n; i > rp; i--) tr(i) != tr(n) && !d1 && (d1 = i), suf[tr(i)] = i;
for (int i = 0; i < 9; i++) c0 += (bool)pre[i], c1 += (bool)suf[i];
if (lp == rp) { flag |= (c0 != 1 || (tr(1) != 2 && tr(1) != 6)) && (c1 != 1 || (tr(n) != 2 && tr(n) != 6)); goto END; }
if (cx(a[lp].x) == 1)
{
if (c0 != 1 || (tr(1) != 2 && tr(1) != 6)) a0[0] = a0[2] = 1;
else a0[tr(1) / 2 - 1] = 1;
}
else
{
a0[cx(a[lp].x)] = c0 != 1 || !pre[6 - 2 * cx(a[lp].x)];
a0[2 - cx(a[lp].x)] = pre[6 - 2 * cx(a[lp].x)] && (pre[6 - 2 * cx(a[lp].x)] != d0 || tr(1) != cx(a[lp].x) * 2 + 2);
}
if (cy(a[rp].y) == 1)
{
if (c1 != 1 || (tr(n) != 2 && tr(n) != 6)) a1[0] = a1[2] = 1;
else a1[3 - tr(n) / 2] = 1;
}
else
{
a1[cy(a[rp].y)] = c1 != 1 || !suf[cy(a[rp].y) * 2 + 2];
a1[2 - cy(a[rp].y)] = suf[cy(a[rp].y) * 2 + 2] && (suf[cy(a[rp].y) * 2 + 2] != d1 || tr(n) != 6 - 2 * cx(a[rp].y));
}
if ((a0[0] && a1[0]) || (a0[2] && a1[2])) { flag = 1; goto END; }
memset(pre, -1, sizeof(pre));
for (int i = lp + 1; i < rp; i++) pre[tr(i)] = 0;
flag |= !((pre[3] && pre[4] && pre[6] && pre[7]) || (pre[1] && pre[2] && pre[4] && pre[5]));
}
END:
if (flag) cout << _ << ' ';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 11
Accepted
time: 1ms
memory: 5728kb
input:
2 10 171631799 561094698 171631799 867698918 126573648 561094698 171631799 867698918 171631799 561094698 126573648 561094698 126573648 561094698 171631799 561094698 126573648 561094698 126573648 561094698 126573648 561094698 171631799 561094698
output:
2 3 6 10
result:
ok 4 number(s): "2 3 6 10"
Test #2:
score: 11
Accepted
time: 1ms
memory: 5636kb
input:
3 10 713180371 43103927 713180371 136832929 853543805 251852293 892623928 251852293 713180371 136832929 713180371 43103927 853543805 43103927 892623928 136832929 713180371 43103927 853543805 43103927 892623928 136832929 713180371 43103927 892623928 251852293
output:
2 3 6 9
result:
ok 4 number(s): "2 3 6 9"
Test #3:
score: 11
Accepted
time: 1ms
memory: 5672kb
input:
4 10 254412080 855555783 254412080 534954259 610506813 184822793 804271098 233942602 804271098 233942602 536633825 184822793 254412080 855555783 804271098 233942602 536633825 233942602 254412080 855555783 804271098 534954259 610506813 534954259 536633825 184822793 536633825 855555783
output:
1 3 4 6 7 8
result:
ok 6 numbers
Test #4:
score: 11
Accepted
time: 1ms
memory: 5708kb
input:
5 10 148547041 170447714 617759855 170447714 617759855 963162312 148547041 948767426 423489361 460053818 423489361 460053818 817714720 948767426 617759855 673099807 617759855 963162312 617759855 673099807 423489361 460053818 423489361 460053818 817714720 948767426 817714720 170447714 148547041 67309...
output:
1 4 6 7
result:
ok 4 number(s): "1 4 6 7"
Test #5:
score: 11
Accepted
time: 1ms
memory: 5676kb
input:
6 10 452189481 369706489 974106249 369706489 152471743 55874110 152471743 7767562 623180600 783682263 116778263 783682263 974106249 369706489 452189481 7767562 623180600 7767562 116778263 783682263 330861484 7767562 452189481 640079581 974106249 640079581 623180600 783682263 974106249 7767562 116778...
output:
1 4 8
result:
ok 3 number(s): "1 4 8"
Test #6:
score: 11
Accepted
time: 1ms
memory: 5612kb
input:
7 10 546365360 29458595 459505526 682968936 892069847 113227141 892069847 682968936 459505526 895773339 436538726 29458595 892069847 29458595 892069847 21442381 200908509 682968936 84249914 782064261 691849455 682968936 691849455 682968936 691849455 21442381 691849455 682968936 691849455 21442381 84...
output:
result:
ok 0 number(s): ""
Test #7:
score: 11
Accepted
time: 1ms
memory: 5680kb
input:
8 10 53884460 816621582 931458006 534340303 53884460 621933704 317941616 487589985 53884460 793793344 831491668 487589985 53884460 816621582 53884460 417129074 831491668 417129074 317941616 534340303 395845824 793793344 395845824 417129074 317941616 166559933 100528187 487589985 83144683 816621582 8...
output:
2 10
result:
ok 2 number(s): "2 10"
Test #8:
score: 11
Accepted
time: 1ms
memory: 5672kb
input:
9 10 703128946 628411749 703128946 876135124 678057110 783023566 563107567 908344997 255577987 177945114 703128946 177945114 519769912 951772210 678057110 470396423 703128946 470396423 563107567 783023566 813952930 470396423 230207898 177945114 230207898 628411749 519769912 555485281 703128946 78302...
output:
1 6
result:
ok 2 number(s): "1 6"
Test #9:
score: 11
Accepted
time: 1ms
memory: 5764kb
input:
10 10 411828800 587312736 368564282 297078085 368564282 265187364 287645241 405039514 368564282 535066135 368564282 265187364 701629305 581674146 894581821 581674146 600278299 347261251 368564282 390901645 633230417 151902557 287645241 297078085 1782717 405039514 287645241 587312736 894581821 587312...
output:
2 5 7
result:
ok 3 number(s): "2 5 7"
Test #10:
score: 11
Accepted
time: 0ms
memory: 3636kb
input:
11 10 594865443 637250974 223004376 637250974 785025296 887146590 120666718 887146590 31665956 652873089 594865443 887146590 1682073 112213166 31665956 121276446 785025296 121276446 28305142 652873089 28305142 661968377 1682073 120498688 938018458 887146590 120666718 112213166 28305142 112213166 223...
output:
10
result:
ok 1 number(s): "10"
Test #11:
score: 11
Accepted
time: 0ms
memory: 3628kb
input:
12 10 39186066 168002748 671722214 32295292 39186066 469855569 442075770 469855569 689698028 968471023 3489285 168002748 671722214 968471023 182809077 689539890 481317320 742954502 265274602 32295292 265274602 26013512 481317320 742954502 976556207 168425358 689698028 32295292 749415058 545907259 24...
output:
10
result:
ok 1 number(s): "10"
Test #12:
score: 11
Accepted
time: 1ms
memory: 5708kb
input:
13 10 527355089 377970728 552459003 455747923 709625462 510634723 552459003 377970728 731571039 951161417 232811148 951161417 552459003 658700181 232811148 377970728 518940837 455747923 455586174 378372201 219157258 378372201 219157258 377970728 709625462 385691279 455586174 510634723 915002219 1039...
output:
1 4 7 8 10
result:
ok 5 number(s): "1 4 7 8 10"
Test #13:
score: 11
Accepted
time: 1ms
memory: 5708kb
input:
14 10 118092342 284486250 927338949 433938384 402661724 978896809 647730583 672355271 31848729 951232518 735207774 379785691 647730583 976797409 118092342 976797409 16895438 951232518 266079358 317991591 402661724 759687663 927338949 672355271 384578818 379785691 927338949 675446949 647730583 672355...
output:
1 2 9
result:
ok 3 number(s): "1 2 9"
Test #14:
score: 11
Accepted
time: 0ms
memory: 3628kb
input:
15 10 180664786 545082798 348151122 545082798 945365791 568927334 87112728 22695274 969050024 993697033 76897725 568927334 946081941 721317554 736012091 124380018 76897725 993697033 969050024 297352406 87112728 22695274 477303819 152140956 497190005 127179215 477303819 957952273 946081941 297352406 ...
output:
2 3
result:
ok 2 number(s): "2 3"
Test #15:
score: 11
Accepted
time: 1ms
memory: 5668kb
input:
16 10 950185079 359470460 717527338 766264034 950185079 464367361 702133494 562464640 47221737 933850433 804214161 68526353 835127535 923127189 663871966 429877028 663871966 933850433 663871966 860592052 717527338 159513156 817202184 970491880 835127535 475614319 519002985 475614319 109565532 137441...
output:
5 9
result:
ok 2 number(s): "5 9"
Test #16:
score: 11
Accepted
time: 0ms
memory: 3696kb
input:
17 10 785164241 654900960 360828785 824839755 439791874 641288092 577364156 862808499 668131950 862808499 893897612 712643610 893897612 596494049 736363695 306279255 668131950 262689126 141356696 306279255 141356696 559915287 785164241 712643610 785164241 862808499 785164241 91314622 657093012 89959...
output:
1 2 4 7 8
result:
ok 5 number(s): "1 2 4 7 8"
Test #17:
score: 11
Accepted
time: 1ms
memory: 5620kb
input:
18 10 634436200 539568435 939344787 325688918 488541626 821095697 430879210 182007328 634436200 676635380 863100947 105320937 634436200 259039153 155697449 650750783 863100947 290661066 904360323 275647130 148773803 836392810 155697449 275647130 904360323 325688918 242889289 395936619 863100947 8363...
output:
4 5 8 10
result:
ok 4 number(s): "4 5 8 10"
Test #18:
score: 11
Accepted
time: 0ms
memory: 5572kb
input:
19 10 643978171 286398879 496772316 971744093 955019965 629209809 874944857 162312003 813096582 680350320 973954693 690315188 387049024 971744093 817521662 629209809 17782710 227578391 308611155 855159132 817521662 286398879 222858816 971744093 222858816 532541541 704414451 629209809 17782710 227578...
output:
result:
ok 0 number(s): ""
Test #19:
score: 11
Accepted
time: 1ms
memory: 5672kb
input:
20 10 339497023 613254335 277080109 869002717 498404000 182716214 838620251 613254335 774235215 599908689 321477480 52537358 406499846 787324761 498404000 867048589 339497023 265303890 653823018 594937507 277080109 856711907 774235215 150629026 339497023 613254335 845764830 867048589 339497023 85671...
output:
5 9
result:
ok 2 number(s): "5 9"
Test #20:
score: 11
Accepted
time: 1ms
memory: 5612kb
input:
2 1 573537298 133184345 819019960 446972624 573537298 133184345
output:
1
result:
ok 1 number(s): "1"
Test #21:
score: 11
Accepted
time: 1ms
memory: 5608kb
input:
2 10 215463781 963544789 417194171 381706359 215463781 381706359 417194171 963544789 417194171 381706359 215463781 381706359 215463781 381706359 215463781 381706359 417194171 963544789 215463781 381706359 417194171 963544789 215463781 381706359
output:
1 2 4 5 6 7 8 9 10
result:
ok 9 numbers
Test #22:
score: 11
Accepted
time: 1ms
memory: 5700kb
input:
2 10 347064832 492954369 276208042 238639351 347064832 492954369 276208042 492954369 347064832 238639351 276208042 492954369 276208042 238639351 276208042 492954369 347064832 492954369 276208042 492954369 347064832 238639351 347064832 492954369
output:
1 5 7 10
result:
ok 4 number(s): "1 5 7 10"
Test #23:
score: 11
Accepted
time: 1ms
memory: 5672kb
input:
2 10 59424469 214378961 467302957 920237929 467302957 214378961 467302957 920237929 467302957 214378961 467302957 920237929 467302957 214378961 467302957 214378961 467302957 920237929 467302957 214378961 467302957 920237929 467302957 920237929
output:
2 4 7 9 10
result:
ok 5 number(s): "2 4 7 9 10"
Test #24:
score: 11
Accepted
time: 1ms
memory: 5676kb
input:
3 10 199016579 737474160 269172900 902060853 363682951 999857037 199016579 999857037 363682951 737474160 363682951 737474160 199016579 737474160 363682951 999857037 363682951 902060853 363682951 737474160 199016579 737474160 269172900 902060853 269172900 737474160
output:
4 5 8 9
result:
ok 4 number(s): "4 5 8 9"
Test #25:
score: 11
Accepted
time: 1ms
memory: 5636kb
input:
3 10 546485825 847511917 181508698 729251744 262746395 577803673 546485825 729251744 546485825 577803673 262746395 847511917 546485825 729251744 546485825 577803673 262746395 577803673 546485825 847511917 262746395 577803673 181508698 847511917 181508698 577803673
output:
6 7 8 10
result:
ok 4 number(s): "6 7 8 10"
Test #26:
score: 11
Accepted
time: 0ms
memory: 5700kb
input:
3 10 237380807 513263480 564217004 186570115 980960156 646344876 980960156 646344876 237380807 646344876 980960156 646344876 980960156 513263480 980960156 513263480 564217004 513263480 980960156 186570115 237380807 513263480 237380807 513263480 980960156 186570115
output:
1 3 6 8 9
result:
ok 5 number(s): "1 3 6 8 9"
Test #27:
score: 11
Accepted
time: 0ms
memory: 5616kb
input:
15 10 624534653 795252871 948654092 55283897 925850942 516359844 291755097 717356990 550592491 128816565 821582441 517445939 994534468 342358076 26658991 396148487 649608935 585141111 323180864 608811044 265317796 85810941 124933870 521198693 547685531 600579720 271150336 559571739 242219192 7700636...
output:
1 2 3 4 8 9
result:
ok 6 numbers
Test #28:
score: 0
Wrong Answer
time: 1ms
memory: 5728kb
input:
16 10 83190470 209266752 880371594 540332431 77621971 311011586 207583928 515840494 210164058 16324657 557379175 66621069 583090455 503874482 155148044 798469757 997210630 599613989 425284838 540392415 814293641 704949575 371097849 755590192 748854182 185159646 764105570 723184963 281807551 22356411...
output:
1 3 4 5 6 7 9 10
result:
wrong answer 2nd numbers differ - expected: '2', found: '3'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%