QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#311255 | #7795. 茧 | zyc070419 | 30 | 297ms | 106572kb | C++14 | 2.9kb | 2024-01-22 09:35:49 | 2024-01-22 09:35:50 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 3;
const ll MX = (1ll << 60);
inline int read() {
char ch = getchar(); int x = 0;
while (!isdigit(ch)) {ch = getchar();}
while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
return x;
}
inline ll Read() {
char ch = getchar(); ll x = 0;
while (!isdigit(ch)) {ch = getchar();}
while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
return x;
}
ll mx;
int T, n, k, sum;
vector<ll> vec[N];
bool tag = true;
namespace subtask1 {
bool cnt[60], pd;
bool check() {return k == 1;}
void solve() {
ll y, res;
for (int qwq = 1; qwq <= T; ++qwq) {
pd = false;
for (int i = 0; i < 60; ++i) cnt[i] = 0;
for (auto x : vec[qwq]) {
for (int j = 0; j < 60; ++j) {
y = (1ll << j);
res = (x / (y << 1)) * y;
if ((x >> j) & 1ll) res += (x & (y - 1)) + 1;
if (res & 1) cnt[j] ^= 1;
}
}
for (int i = 0; i < 60; ++i) pd |= cnt[i];
puts(pd ? "Lily" : "Kaguya");
}
}
}
namespace subtask2 {
const int M = (1 << 22) - 1;
const int W = (1 << 22) + 3;
int a[W];
bool check() {return mx <= M;}
void solve() {
a[0] = 0; int lst = 0, x;
for (int i = 1;; ++i) {
x = 1;
for (int j = 1; j <= k; ++j) x *= i;
for (int j = lst + 1 ; j < x && j <= M; ++j) a[j] = a[j - i];
if (x <= M) a[lst = x] = i;
else break;
}
for (int i = 1; i <= M; ++i) a[i] ^= a[i - 1];
int res;
for (int qwq = 1; qwq <= T; ++qwq) {
res = 0;
for (auto x : vec[qwq]) res ^= a[x];
puts(res ? "Lily" : "Kaguya");
}
}
}
namespace subtask3 {
vector<ll> pw;
map<ll, int> mp;
bool check() {return tag && mx < (1ll << 32) && sum <= 1000;}
int calc(ll x) {
if (mp.count(x)) return mp[x];
int pos;
if (k > 2) pos = upper_bound(pw.begin(), pw.end(), x) - pw.begin() - 1;
else pos = sqrt(x);
ll y = (x - pw[pos]) % (pos + 1) + pw[pos];
if (y == pw[pos]) return pos;
return mp[x] = calc(y - pos - 1);
}
void solve() {
int res;
for (int i = 0;; ++i) {
ll x = 1;
for (int j = 1; j <= k; ++j) x = min(x * i, mx + 1);
if (x > mx) break;
pw.push_back(x);
}
for (int qwq = 1; qwq <= T; ++qwq) {
res = 0;
for (int i = 1; i < vec[qwq].size(); i += 2) res ^= calc(vec[qwq][i]);
puts(res ? "Lily" : "Kaguya");
}
}
}
int main() {
T = read(); k = read(); ll x;
for (int i = 1; i <= T; ++i) {
n = read(); sum += n; tag &= (n % 2 == 0);
while (n--) x = Read(), vec[i].push_back(x), mx = max(mx, x);
if (tag) for (int j = 0; j < vec[i].size(); j += 2) tag &= (vec[i][j] + 1 == vec[i][j + 1]);
}
if (subtask1 :: check()) subtask1 :: solve();
else if (subtask2 :: check()) subtask2 :: solve();
else if (subtask3 :: check()) subtask3 :: solve();
return 0;
}
/*
1 2
10
6 7 9 10 17 18 2 3 24 25
*/
详细
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 31ms
memory: 8832kb
input:
1136 1 1 113619249930092995 2 457093394163961514 36523281 2 52273 586907144813890981 149 13412372218 128311326 618178541606515600 756479282467845696 276251850291230545 978441742104676009 1035439042005099 1105099328508110145 981121546786695466 97032240925148816 171 149766413231751232 28137602525069 9...
output:
Kaguya Lily Kaguya Lily Lily Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Lily Kaguya Kaguya Kaguya Lily Lily Lily Lily Kaguya Kaguya Lily Lily Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Lily Kaguya Lily Kaguya Kaguya Kaguya Lily Kaguya Lily Kaguya Kaguya Lily L...
result:
ok 1136 tokens
Subtask #2:
score: 5
Accepted
Test #2:
score: 5
Accepted
time: 7ms
memory: 23636kb
input:
9868 2 6 45196 27174 14224 5578 40059 47649 8 38740 7 56634 37760 43117 57202 349 102 7 47 498 25922 50544 13 48434 12 11 59314 45 4091 47301 3701 38642 253 11 48627 30158 36 4 1209 43050 22162 22239 12 5 64446 660 18577 46228 48927 6 47617 55178 30917 45801 8 8 60993 148 109 37947 19683 2613 3278 1...
output:
Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Lily Lily Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Lily Lily Lily Kaguya Kaguya Kaguya Kaguya Kaguya Lily Lily Kaguya Kaguya Kaguya Kaguya Kaguya Lily Kaguya Lily Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Lily Lily Kaguya ...
result:
ok 9868 tokens
Test #3:
score: 0
Accepted
time: 7ms
memory: 23648kb
input:
14255 3 2 25431 1431 9 6455 6976 25699 5 64472 6603 40 38 14 16 55580 48907 4456 10524 42216 47 63931 63762 53439 26656 34 44195 2043 8761 27558 36 20 44674 37691 48056 15873 52517 57044 5922 61629 15692 3 62877 10974 6 4507 23119 34595 23 2717 58541 1857 1 45217 8 61934 53794 1102 50 40833 35001 37...
output:
Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Lily Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Lily Kaguya Kaguya Lily Kaguya Lily Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Lily Kaguya Kaguya Lily Kagu...
result:
ok 14255 tokens
Test #4:
score: 0
Accepted
time: 8ms
memory: 23736kb
input:
22059 4 3 16 134 1 5 46554 7709 268 4 36331 6 19728 61853 17949 7 4855 38920 2 1 35389 2 15749 41751 5 32063 47259 1078 56138 16362 3 2009 4599 23517 4 33 200 3038 15556 2 1 401 2 3245 65166 3 21532 2478 25347 2 2809 10699 6 25271 2005 43749 9 5 41206 2 30434 87 6 47897 478 1684 174 14290 961 3 3387...
output:
Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Lily Lily Kaguya Kaguya Kaguya Kaguya Lily Kaguya Kaguya Kaguya Kaguya Lily Kaguya Kaguya Lily Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Lily Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Lily Kaguya Kaguya...
result:
ok 22059 tokens
Test #5:
score: 0
Accepted
time: 8ms
memory: 23796kb
input:
22872 5 5 2 37314 15910 93 7338 5 26212 55591 69 1857 8051 2 31713 2 2 2135 2118 3 13642 2034 59512 1 217 7 55365 2284 1 24506 33610 57519 10075 1 433 3 59 52 1572 7 10554 65 3 7622 24964 11 25621 10 39719 29778 48994 182 42292 48025 4070 59304 58958 4186 2 28524 2 1 27728 8 29032 28789 1 178 766 34...
output:
Lily Lily Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Lily Kaguya Kaguya Kaguya Kaguya Kaguya Lily Kaguya Kaguya Kaguya Kaguya Kaguya Lily Lily Kaguya Lily Kaguya Kaguya Lily Kaguya Kaguya Lily Lily Kaguya Lily Kaguya Kaguya Kaguya Kaguya Kaguya Lily Kaguya Kaguya Kaguya Kaguya Ka...
result:
ok 22872 tokens
Subtask #3:
score: 10
Accepted
Dependency #2:
100%
Accepted
Test #6:
score: 10
Accepted
time: 8ms
memory: 23572kb
input:
6839 2 17 224984 2 833273 2067770 338355 901894 1679997 133482 3910338 204 66192 1011364 37 128 20 949106 1195015 15 634678 297242 115 1061781 996944 4 427042 1212821 6175 84 289 2568587 5500 1496533 3581457 6 281854 3131119 1496695 10164 133 3317 15 34562 74 3521796 863475 3344736 453013 23 1994270...
output:
Kaguya Kaguya Kaguya Lily Lily Kaguya Kaguya Lily Kaguya Lily Lily Kaguya Kaguya Kaguya Kaguya Kaguya Lily Lily Lily Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Lily Kaguya Kaguya Kaguya Lily Kaguya Kaguya Kaguya Kaguya Lily Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Lily Ka...
result:
ok 6839 tokens
Test #7:
score: 0
Accepted
time: 8ms
memory: 23556kb
input:
10017 3 6 568016 487338 4070627 27 3859427 4384 1 789275 2 167 51 2 11869 1 19 2378345 44494 705262 2061753 3131409 2 2 2332606 1935304 3056056 502475 3876757 332052 3101503 813 1493744 4260 387489 82859 3 205205 16529 4125531 29 40208 1766700 397131 1152394 103926 2 163083 4 3909408 3553066 3998082...
output:
Kaguya Kaguya Kaguya Kaguya Lily Kaguya Lily Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Lily Kaguya Lily Kaguya Kaguya Kaguya Lily Lily Kaguya Kaguya Kaguya Lily Kaguya Lily Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Lily Lily Kaguya Kaguya Kaguya Lily ...
result:
ok 10017 tokens
Test #8:
score: 0
Accepted
time: 8ms
memory: 23580kb
input:
13927 4 7 92 3883763 88110 2 2313854 108102 41129 2 5 25334 8 1528214 1137 2505858 2387 2253451 1563671 2743087 225373 5 1156685 532264 2373059 2126678 3240826 9 111625 2389 247 3992621 4448 128613 2920953 1099070 103458 21 3390 20 19816 24729 3793052 3365319 3712556 2547516 2 1742810 503602 1 94909...
output:
Lily Kaguya Lily Lily Lily Kaguya Kaguya Lily Kaguya Lily Lily Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Lily Lily Kaguya Kaguya Lily Lily Kaguya Kaguya Kaguya Lily Kaguya Kaguya Kaguya Kaguya Lily Kaguya Kagu...
result:
ok 13927 tokens
Test #9:
score: 0
Accepted
time: 6ms
memory: 23648kb
input:
18003 5 2 833877 1803069 1 4 1 4446 17 12612 1756224 233 315585 47983 1432 967831 1176615 2465654 53241 188 55972 4793 3896048 3795886 805349 2441141 7 1408978 22493 2312 489 1406745 428988 596505 3 142741 3467 3243 7 903354 3 6253 1616 3836996 340 3949022 1 4087622 9 1 1175749 3811867 419872 415396...
output:
Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Lily Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Lily Lily Kaguya Lily Kaguya Kaguya Kaguya Kaguya Lily Kaguya Kaguya Kaguya Lily Kaguya Kaguya Lily Kaguya Lily Kaguya Kaguya Kaguya Lily Kaguya Kaguya Kaguya Lily Kaguy...
result:
ok 18003 tokens
Subtask #4:
score: 10
Accepted
Test #10:
score: 10
Accepted
time: 297ms
memory: 106572kb
input:
500 2 2 37980539 37980540 2 193 194 2 643 644 2 3409676912 3409676913 2 537559 537560 2 374273640 374273641 2 7 8 2 3795849784 3795849785 2 79614 79615 2 3438078922 3438078923 2 3757510845 3757510846 2 1 2 2 1824633835 1824633836 2 1 2 2 55 56 2 714486861 714486862 2 2772062264 2772062265 2 14788368...
output:
Kaguya Kaguya Kaguya Kaguya Lily Kaguya Kaguya Kaguya Lily Lily Lily Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Lily Kaguya Lily Kaguya Kaguya Kaguya Lily Kaguya Lily Kaguya Lily Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Lily Lily Kaguya Kaguya Kaguya Kaguya Kaguya ...
result:
ok 500 tokens
Test #11:
score: 0
Accepted
time: 12ms
memory: 9584kb
input:
500 3 2 1321906355 1321906356 2 72 73 2 3261 3262 2 3 4 2 233038343 233038344 2 48806099 48806100 2 3093435489 3093435490 2 1 2 2 2529852032 2529852033 2 2448664571 2448664572 2 116570 116571 2 3544932649 3544932650 2 1982289066 1982289067 2 8 9 2 1714949081 1714949082 2 1850902999 1850903000 2 5 6 ...
output:
Kaguya Lily Lily Kaguya Kaguya Kaguya Lily Kaguya Kaguya Lily Kaguya Kaguya Lily Kaguya Kaguya Kaguya Kaguya Lily Kaguya Kaguya Kaguya Kaguya Lily Kaguya Kaguya Kaguya Kaguya Kaguya Lily Kaguya Kaguya Kaguya Kaguya Lily Kaguya Kaguya Kaguya Kaguya Kaguya Kaguya Lily Kaguya Lily Kaguya Lily Kaguya Ka...
result:
ok 500 tokens
Subtask #5:
score: 0
Time Limit Exceeded
Dependency #4:
100%
Accepted
Test #12:
score: 0
Time Limit Exceeded
input:
25 2 40 32765 32766 3342432694 3342432695 2317586775 2317586776 36296128 36296129 2133632147 2133632148 58935 58936 1544281865 1544281866 1239424 1239425 3030161418 3030161419 2830847513 2830847514 2882661816 2882661817 145 146 3989168095 3989168096 1 2 1412485952 1412485953 10 11 76543 76544 14 15 ...
output:
result:
Subtask #6:
score: 0
Wrong Answer
Test #16:
score: 0
Wrong Answer
time: 3ms
memory: 8756kb
input:
1169 2 98 2052761 2052762 861925831649843897 861925831649843898 1031265876706940814 1031265876706940815 617144630657193626 617144630657193627 72 73 138103 138104 156743812713553 156743812713554 205151719721047118 205151719721047119 1065302803446555430 1065302803446555431 1545284063203 1545284063204 ...
output:
result:
wrong answer Unexpected EOF in the participants output
Subtask #7:
score: 0
Wrong Answer
Test #17:
score: 0
Wrong Answer
time: 6ms
memory: 8300kb
input:
1775 3 56 1113086767934729403 1113086767934729404 395289496182979739 395289496182979740 1036610723921853591 1036610723921853592 273906 273907 1081906643487536771 1081906643487536772 442413497681636481 442413497681636482 13354476004 13354476005 477736247131002 477736247131003 6159425067 6159425068 5 ...
output:
result:
wrong answer Unexpected EOF in the participants output
Subtask #8:
score: 0
Wrong Answer
Test #18:
score: 0
Wrong Answer
time: 1ms
memory: 6264kb
input:
47 2 15 226 33559 101516630 2758718 1497465096 143 10221 19229493 2 19317677 2599390763 2043194 462237450 4045936184 209655973 24 1951804242 97 1448079073 419079478 1033169500 1875 2482 2350383606 16 3958107653 2574141589 2934502110 2036 2574986227 1794970348 4009429601 2844472951 155702147 18791465...
output:
result:
wrong answer Unexpected EOF in the participants output
Subtask #9:
score: 0
Wrong Answer
Test #19:
score: 0
Wrong Answer
time: 1ms
memory: 6112kb
input:
71 3 20 1902494844 129105842 1836429008 2862717739 3767166853 2686186537 1099034 40 344827 734438640 2231265370 2818449793 114955743 540338925 553099374 9179 2122555208 580 371 1909359957 30 18 2762110981 262509769 2811288568 3618225103 47784509 255418873 4040384827 159350 87784115 1619856413 8813 1...
output:
result:
wrong answer Unexpected EOF in the participants output
Subtask #10:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #5:
0%