QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#217743 | #5024. 【模板】双端队列 | cyb1010 | 100 ✓ | 41ms | 4012kb | C++14 | 2.6kb | 2023-10-17 11:45:21 | 2023-10-17 11:45:22 |
Judging History
answer
/**
* @author : cyb1010
* @date : 2023-10-17 09:04:56
* @file : game.cpp
*/
#include <bits/stdc++.h>
using namespace std;
namespace FastIO {
const std::size_t buf_size = 1 << 18;
char I[buf_size], *p1, *p2, O[buf_size], s[128];
int p, q, f;
inline char gc() {
return p1 == p2 && (p2 = (p1 = I) + fread(I, 1, sizeof(I), stdin), p1 == p2)
? EOF
: *p1++;
}
inline void pc(char c) { O[p++] = c; }
inline void flush() { fwrite(O, 1, p, stdout), p = 0; }
void chkf() {
if (p >= buf_size >> 1) flush();
}
struct AutoFlush {
~AutoFlush() { flush(); }
} auto_flush;
template <typename T>
void rd(T &x) {
char c = gc();
x = 0, f = c == '-';
while (!isdigit(c)) c = gc(), c == '-' ? f = 1 : 0;
while (isdigit(c)) x = x * 10 + c - '0', c = gc();
f ? x = -x : 1;
}
template <typename T>
void wr(T x) {
if (x < 0) x = -x, pc('-');
do s[++q] = (x % 10) | 48;
while (x /= 10);
do pc(s[q]);
while (--q);
chkf();
}
template <typename T>
void wr(T x, char c) {
wr(x), pc(c);
}
} // namespace FastIO
using FastIO::rd;
using FastIO::pc;
using FastIO::chkf;
#define fo(s) freopen(s ".in", "r", stdin), freopen(s ".out", "w", stdout)
#define fi first
#define se second
typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
int __, _, n, x, a[100010];
#define wrf pc('F'), pc('i'), pc('r'), pc('s'), pc('t'), pc('\n'), chkf()
#define wrs \
pc('S'), pc('e'), pc('c'), pc('o'), pc('n'), pc('d'), pc('\n'), chkf()
#define wrd pc('D'), pc('r'), pc('a'), pc('w'), pc('\n'), chkf()
bool chk_3() {
for (int i = 2; i < n; i += 2)
if (a[i] != a[i - 1]) return false;
x = 0;
for (int i = 2; i < n; i += 2) x ^= a[i];
return (((x ^ a[n]) > x) ? (wrf) : (wrs)), true;
}
bool chk_t(int l, int r) {
for (int i = l; i < r; i += 2)
if (a[i] != a[i + 1]) return false;
return true;
}
bool chk(int l, int r) {
int x = l, y = 0;
for (int i = l; i <= r; i++) y += a[i];
if (y & 3) return false;
while (a[l] == a[r] && l < r) l++, r--;
return chk_t(l, r) || (x < l && chk_t(l - 1, r + 1));
}
void work() {
rd(n), x = 0;
for (int i = 1; i <= n; i++) rd(a[i]), x ^= a[i];
if (!x) return wrd;
if (!(n & 1)) return wrf;
if (chk_3()) return;
x = __lg(x);
for (int i = 1; i <= n; i++) a[i] = (a[i] >> x) & 1;
if (chk(1, n - 1) || chk(2, n)) return wrf;
wrs;
}
int main() {
// fo("game");
rd(_);
while (_--) work();
return 0 ^ __ ^ 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 15
Accepted
Test #1:
score: 15
Accepted
time: 1ms
memory: 3456kb
input:
40 15 1042186166 1065050038 1052442342 117744385 1044381358 996146407 947617159 1031691934 27328777 130294601 1065311743 1065082111 12845136 941620871 1042177446 15 1068465534 15766217 69219008 95461385 1048542590 1051709438 1048575351 1072652151 978275647 1044381687 999247358 1062194999 1054829887 ...
output:
Second Second Second First First Second Second Draw Draw Draw Draw Second Second Second Second First First Draw Second Second Second Draw Second Draw Draw First Second Second Draw Second First First Second Second First First Second First First Draw
result:
ok 40 tokens
Subtask #2:
score: 20
Accepted
Test #2:
score: 20
Accepted
time: 1ms
memory: 3700kb
input:
40 987 1073733087 9437225 570431533 1031755263 1031755251 579873284 571521061 536872960 546353705 43000364 535780827 1065313790 536834043 41953824 503270871 1040175099 8426021 537960961 1054732 545292837 34648585 34603052 546314244 537965060 9439748 41953292 43037189 9447949 536864767 1073698294 503...
output:
Second Second First Second First Second Second First Second First Draw First Second First First Second Second Second Draw Draw Draw Draw First Second Second Second Second First Second Second Draw Second First Second First Draw Second First First First
result:
ok 40 tokens
Test #3:
score: 0
Accepted
time: 1ms
memory: 3848kb
input:
40 985 1051584087 161093905 991143886 498485632 221004168 788260831 916059871 274356401 213536945 95177001 98458032 869773278 787854966 1051043535 603582199 3672200 216942729 975171167 93067289 603832174 292948248 602275551 354556312 4589841 22567337 428083233 89540913 589692543 361906352 77353112 9...
output:
Second First Draw Second First Second Draw First First Second First Draw First First Draw Second First Second Second Draw First First First Second Second Second Draw First Second Second First Second First Second First First Second First First First
result:
ok 40 tokens
Subtask #3:
score: 25
Accepted
Test #4:
score: 25
Accepted
time: 20ms
memory: 3884kb
input:
40 49999 30704571 23631198 10459697 452884 909025 3745220 5633170 29257098 24428644 21991837 21100897 21249665 18667093 13809790 21220831 32750672 29531337 31709216 17139349 4444339 787544 14509794 3855820 201034 13281440 26541636 31476242 10318360 20485824 26793325 8264891 22349828 20554718 7556006...
output:
Second First Second Second First Second Second First Second Second Second First First First Second Second Second Second First First Second Second Second Second First First Second First Second First First First First Second First Second First First First First
result:
ok 40 tokens
Test #5:
score: 0
Accepted
time: 26ms
memory: 3996kb
input:
40 50000 32128601 23900639 9898059 10642201 2516432 19994626 8905808 23168114 27093651 32766595 7092623 14455293 32272254 11330578 25018676 9383756 16276912 15628227 6205425 11630483 19952395 19133325 22760569 7587885 30335157 13910732 11179526 4266775 18282905 14622912 11401940 33485172 9826535 292...
output:
First Second First First Second Second Second Second Second First Second First First First First Second First Second First First First Second First First First Second First First Second Second Second First First First First First First Second First Second
result:
ok 40 tokens
Subtask #4:
score: 40
Accepted
Test #6:
score: 40
Accepted
time: 27ms
memory: 3884kb
input:
40 49035 1073176430 531291499 1005508607 675350672 368768 867368831 139504132 1321089 134482448 464248170 1068169195 68946580 469491567 738764816 742459920 535197167 531887598 672172545 609558673 608209040 335282031 532674543 72878741 610117777 138447508 398155759 71608464 672172165 402325355 609845...
output:
First Second First First Second Second Draw First Second Draw First First First Second First First First Second First Draw First First Draw Second First Second Second Second Second Second First Draw First First Second First First First First First
result:
ok 40 tokens
Test #7:
score: 0
Accepted
time: 26ms
memory: 4012kb
input:
40 49531 1073150907 41944161 41943104 1073725402 1039579067 41943140 543780 1073738686 8930372 1039662046 33573892 1073200030 82948 1064763322 1073738751 34160641 1040120763 8457316 8473636 42467360 8388609 1040169947 42532869 1073656799 41959456 82977 42468453 1039663007 1073722331 8408132 2117 107...
output:
First Draw First First Second Second First First First First First First First Second Draw First Draw Second Second First Second Second First Second First Second Draw Second Second Draw Second Second Draw Second First Second Second First Draw First
result:
ok 40 tokens
Test #8:
score: 0
Accepted
time: 35ms
memory: 4004kb
input:
40 49853 709415352 966616951 540711056 421879407 1063609959 653447600 235563064 576376888 527818615 672723248 544909368 778739848 928978911 891625415 1034942415 182583688 777564552 209768456 650657816 578484608 457017311 176297984 288194151 239237376 1003445863 927270735 1035976423 399464135 7864586...
output:
Second Second First First First Draw Second Draw First Draw Second First Second Second First Second Draw First Second First First Second First First Second Draw First Second Second Draw First Second Second Second Draw Second Second Draw First Second
result:
ok 40 tokens
Test #9:
score: 0
Accepted
time: 29ms
memory: 3840kb
input:
40 49261 425694955 1031784295 503022575 109335829 614742016 970713959 2371605 503295718 1006601199 526379886 581191837 1037823715 69226905 537145497 612639104 972802786 648040832 536868474 536590183 8661128 1071641595 547621905 109344004 461356799 459259755 612380697 10492304 1038079850 492562410 57...
output:
First Second First First First First First Second Draw Draw First Draw Second First Second Draw First Draw Second Draw First First Draw First Second First Second Second First First First Second Second Draw Second First Draw Draw Second Draw
result:
ok 40 tokens
Test #10:
score: 0
Accepted
time: 18ms
memory: 3876kb
input:
40 49583 736087491 736099826 922746303 738151902 402653272 853499890 8272 937394070 788520843 218141276 150994964 354456100 920608658 870305695 404750396 738160114 870272958 922705347 287355460 668958670 85983320 736059387 85991532 939482607 853532086 469774361 738160571 719290343 150999589 26848105...
output:
First First First Draw Draw Second First First Draw First Second Second Second First Draw Second Second Second Second Second Draw First Second First Second First Second First Second Second Second Second First Draw Second Draw Second Draw Second Second
result:
ok 40 tokens
Test #11:
score: 0
Accepted
time: 27ms
memory: 3812kb
input:
40 49025 1056947963 814235909 293602565 242661882 16795396 511098874 813696000 553649153 562103809 553731077 804781306 519552763 25690373 796917759 796851710 511115003 788463611 822084357 831012865 259521018 780123647 831078400 267893247 528482043 8471808 25165825 259980026 16794112 294143236 536870...
output:
First Second Second Second First First Second Second Draw Draw First Second First First Draw Second Second Second Draw First Second Second First Second Second First First First Draw Draw First Second First Second Draw Draw Draw First Draw Second
result:
ok 40 tokens
Test #12:
score: 0
Accepted
time: 41ms
memory: 3816kb
input:
40 49791 819003405 281051145 210833420 345018373 392622051 589819872 1004961788 468152307 791080944 61800429 732889056 806391811 813694977 54423523 799997944 134774795 255324134 598179832 608174085 549453824 468713460 792686563 1016168464 523698144 81297412 213979140 949555201 670040041 604606481 60...
output:
Draw Draw First First Second Draw Draw Second Second Second Second First Second Second Second Second First First Draw First First Second Draw Second First First Second Second First Second Draw First Draw Draw Second First Draw First Draw Draw
result:
ok 40 tokens