QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#307587 | #8000. 平方数 | zhouyuhang | 70 | 555ms | 36616kb | C++14 | 1.9kb | 2024-01-18 20:48:03 | 2024-01-18 20:48:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
using i128 = __int128_t;
const int N = 3e5 + 10;
int n;
i128 a[N];
i128 read() {
i128 x = 0; int ch = getchar();
while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
return x;
}
mt19937 Rnd(time(0));
int Rand(int l, int r) { return Rnd() % (r - l + 1) + l;}
bool isPrime(int n) { for (int i = 2; i * i <= n; ++i) if (n % i == 0) return 0; return 1;}
int Pow(int x, int y, int p) {
int r = 1;
for (; y; y >>= 1, x = 1ll * x * x % p) if (y & 1) r = 1ll * r * x % p;
return r;
}
i128 v[N];
vector<i128> val;
vector<int> vec[N];
bool np[N];
int tot = 0, prm[N];
int f[N];
int main() {
n = read();
for (int i = 1; i <= n; ++i) a[i] = read();
for (int t = 0; t < 100; ++t) {
int p = Rand(1e4, 1e5);
while (!isPrime(p)) p = Rand(1e4, 1e5);
f[0] = f[1] = 1, tot = 0;
for (int i = 2; i < p; ++i) {
if (!np[i]) { prm[++tot] = i, f[i] = Pow(i, (p - 1) / 2, p);}
for (int j = 1, t; (t = i * prm[j]) < p; ++j) {
np[t] = 1, f[t] = 1ll * f[i] * f[prm[j]] % p;
if (t % prm[j] == 0) break;
}
}
for (int i = 1; i <= n; ++i) {
v[i] ^= (f[a[i] % p] == 1 ? 0 : (i128)1) << t;
}
}
for (int i = n; i >= 1; --i) v[i] ^= v[i + 1];
for (int i = 1; i <= n + 1; ++i) val.push_back(v[i]);
sort(val.begin(), val.end());
for (int i = 1; i <= n + 1; ++i) v[i] = lower_bound(val.begin(), val.end(), v[i]) - val.begin();
long long ans = 0;
vec[0].push_back(n + 1);
for (int i = n; i >= 1; --i) {
ans += vec[v[i]].size();
vec[v[i]].push_back(i);
}
cout << ans << endl;
int cnt = 1e5;
for (int i = 1; i <= n; ++i) {
vec[v[i]].pop_back();
for (int j = (int)vec[v[i]].size() - 1; j >= 0; --j) {
if (cnt == 0) { return 0;}
cout << i << ' ' << vec[v[i]][j] - 1 << endl;
--cnt;
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 5
Accepted
time: 275ms
memory: 16320kb
input:
100 231 1092 572 688 473 832 2132 861 1092 2132 451 451 861 473 336 473 231 231 832 231 1092 451 861 209 451 399 656 176 1328 3403 176 63 231 123 688 156 48 2236 6 6 231 572 572 231 57 399 48 176 1092 399 572 399 399 209 1743 1577 861 4316 399 451 1328 129 156 688 4316 4316 451 22 42 656 572 832 473...
output:
219 1 3 1 11 1 21 1 28 1 34 1 38 1 40 1 44 1 52 1 64 1 66 1 91 2 8 2 13 2 23 2 41 2 43 2 48 2 54 2 72 2 93 2 100 3 6 3 9 3 19 3 49 4 11 4 21 4 28 4 34 4 38 4 40 4 44 4 52 4 64 4 66 4 91 5 15 5 35 5 63 5 86 6 16 6 18 6 27 6 78 7 9 7 19 7 49 8 10 8 12 8 22 8 26 8 31 8 67 8 77 8 88 9 13 9 23 9 41 9 43 ...
result:
ok 439 numbers
Test #2:
score: 5
Accepted
time: 275ms
memory: 16472kb
input:
100 175 175 423 423 315 1645 423 1067 1067 385 385 2425 2425 423 2400 275 9312 423 423 63 329 3395 960 960 250 423 970 875 4559 385 1067 1645 1067 1056 737 1645 6432 99 875 603 517 2400 1175 3360 670 517 1056 2400 470 63 63 385 225 350 90 2425 873 1645 873 873 960 1645 864 350 4559 250 3395 517 423 ...
output:
190 1 2 1 4 1 7 1 9 1 11 1 13 1 71 3 4 3 7 3 9 3 11 3 13 3 71 4 6 4 14 4 33 5 7 5 9 5 11 5 13 5 71 6 30 6 37 6 49 6 51 6 75 7 14 7 33 8 9 8 11 8 13 8 71 9 18 9 21 10 11 10 13 10 71 11 22 11 24 11 38 11 55 11 57 11 72 11 84 11 93 11 95 11 98 12 13 12 71 14 71 15 33 16 77 17 34 17 78 18 19 18 28 18 32...
result:
ok 381 numbers
Test #3:
score: 5
Accepted
time: 243ms
memory: 14492kb
input:
100 145 145 3976 3976 361 3976 3976 1159 1159 1159 3976 1159 95 95 1073 2257 551 25 1159 1159 1159 1691 445 1349 1624 280 2059 570 1830 3976 3976 1159 1073 445 2581 703 3976 95 3976 900 1159 4331 1064 6319 6319 2581 2581 95 3976 2130 95 1680 5041 1064 1102 2627 3382 95 4984 703 2059 551 2627 1073 28...
output:
282 1 2 1 4 1 5 1 7 1 9 1 38 1 43 1 45 1 47 1 52 1 53 1 69 1 74 1 76 1 79 1 93 2 25 2 62 2 70 2 72 2 99 3 4 3 5 3 7 3 9 3 38 3 43 3 45 3 47 3 52 3 53 3 69 3 74 3 76 3 79 3 93 4 6 4 12 4 14 4 19 4 21 4 27 4 32 4 39 4 40 4 65 4 77 5 5 5 7 5 9 5 38 5 43 5 45 5 47 5 52 5 53 5 69 5 74 5 76 5 79 5 93 6 7 ...
result:
ok 565 numbers
Test #4:
score: 5
Accepted
time: 311ms
memory: 22908kb
input:
100000 490261 103622 581460 82 148675 57960 470171 480754 465750 67894 14094 386906 10507 2253 386074 89318 29184 633445 158738 616183 225862 13528 252387 378575 828099 563268 31578 487411 590795 156306 69611 483536 120028 615414 19244 49885 113293 33947 218039 86557 78069 13129 64829 193152 10489 6...
output:
412 62 3782 96 151 270 270 319 5502 337 1680 367 562 390 390 473 40115 650 650 814 814 923 923 1156 2670 1398 49930 1456 11214 1599 2107 1750 1750 2091 48791 2227 2227 2694 2694 2797 10608 2938 2938 3067 3067 3355 3355 3369 3369 3513 8600 3605 47519 3951 3951 4281 4281 4396 7330 4497 4497 4521 4521 ...
result:
ok 825 numbers
Test #5:
score: 5
Accepted
time: 311ms
memory: 24692kb
input:
100000 67570 484736 520610 35657 3810 433919 234898 100380 364999 387610 203364 324993 3560 53217 324693 348977 456751 49183 149319 269122 252338 180787 146746 111557 60555 8843 352186 280066 23641 16419 341544 163445 103514 71100 37300 7087 757096 121635 375844 210450 21037 294544 205250 34189 6230...
output:
435 47 2598 47 2599 164 3171 313 6765 487 487 540 677 596 1128 668 668 1588 1588 1590 1590 1983 1983 2599 2599 2786 71013 2812 2812 2925 2925 3110 3110 3132 59588 3390 3390 3390 26703 3391 26703 3774 3774 3817 3817 3897 4061 3966 3966 4072 92911 4073 4073 4089 5255 4218 5589 4414 28043 4648 4648 466...
result:
ok 871 numbers
Test #6:
score: 5
Accepted
time: 310ms
memory: 20792kb
input:
100000 18881 262211 537680 17472 378696 709552 94019 77851 30857 149404 649543 170996 771720 10549 516075 228930 277507 624288 276892 297900 307159 359999 361232 113249 77423 147606 423604 84538 156003 90085 327367 855426 827139 61725 185473 372586 208861 231422 265506 141980 374872 1476 38531 54102...
output:
465 84 66713 167 167 206 3836 369 369 491 491 499 499 508 1165 676 7886 705 6687 920 920 1248 2110 1306 1306 1313 1313 1611 1611 2119 2119 2332 2332 2470 2470 2533 9957 2788 2788 2976 2976 3281 3281 3453 85306 3520 3520 3607 3607 3664 13904 3916 5491 3996 3996 4132 94587 4329 4329 4335 4335 4657 509...
result:
ok 931 numbers
Test #7:
score: 5
Accepted
time: 283ms
memory: 14704kb
input:
100 252540522668367800051165503341797101 252540522668367800051165503341797101 515734205540858375230970744185503476 515734205540858375230970744185503476 515734205540858375230970744185503476 20006351115008868016624085151101641 247729772684862577956704436312743764 525749426133479408507862683647100309 2...
output:
268 1 2 1 4 1 9 1 13 1 25 1 27 1 30 1 37 1 39 1 41 1 45 1 57 1 68 1 79 1 93 1 95 1 100 2 8 2 10 2 31 2 44 2 49 2 80 3 4 3 9 3 13 3 25 3 27 3 30 3 37 3 39 3 41 3 45 3 57 3 68 3 79 3 93 3 95 3 100 4 5 4 6 4 20 4 28 4 40 4 69 4 78 4 82 5 9 5 13 5 25 5 27 5 30 5 37 5 39 5 41 5 45 5 57 5 68 5 79 5 93 5 9...
result:
ok 537 numbers
Test #8:
score: 5
Accepted
time: 279ms
memory: 14540kb
input:
100 215586339034581112359324805094546001 303379817540300361137707126338995147 104808748941005778265379001474181311 624037066192891324650526373997894277 25241527443369969985568078141601980 25241527443369969985568078141601980 25241527443369969985568078141601980 246472575163277676212469646102580577 330...
output:
228 1 4 1 6 1 33 1 38 1 60 1 76 1 87 3 10 3 11 3 17 3 28 3 30 3 56 3 58 3 74 3 96 3 98 4 27 4 31 4 32 4 39 4 46 4 52 4 55 4 67 4 79 4 95 4 99 5 6 5 33 5 38 5 60 5 76 5 87 6 7 6 14 6 21 6 26 6 40 6 49 6 64 6 66 6 92 7 33 7 38 7 60 7 76 7 87 8 14 8 21 8 26 8 40 8 49 8 64 8 66 8 92 9 63 10 12 10 24 10 ...
result:
ok 457 numbers
Test #9:
score: 5
Accepted
time: 279ms
memory: 16148kb
input:
100 158537529361366175017273712129860802 158537529361366175017273712129860802 158537529361366175017273712129860802 19229228673961850397142728750194500 19229228673961850397142728750194500 158537529361366175017273712129860802 158537529361366175017273712129860802 146462580301387603768001461232863067 14...
output:
311 1 2 1 6 1 10 1 19 1 50 1 61 1 81 1 83 2 3 2 5 2 7 2 9 2 11 2 13 2 15 2 17 2 21 2 24 2 34 2 36 2 52 2 60 2 62 2 63 2 69 2 88 3 6 3 10 3 19 3 50 3 61 3 81 3 83 4 5 4 7 4 9 4 11 4 13 4 15 4 17 4 21 4 24 4 34 4 36 4 52 4 60 4 62 4 63 4 69 4 88 5 26 5 30 5 42 5 64 6 7 6 9 6 11 6 13 6 15 6 17 6 21 6 2...
result:
ok 623 numbers
Test #10:
score: 5
Accepted
time: 239ms
memory: 16372kb
input:
100 914638941914953504311998276428558213 914638941914953504311998276428558213 747095025403412259040087323520544846 742830945879368908514418916394107478 536433221656876669923408388652526923 522825554970208754487023674878950119 938444400048947160306314773841111921 285959233901776009120253190045112270 ...
output:
285 1 2 1 7 1 27 2 4 2 14 2 16 2 18 2 26 2 30 2 38 2 48 2 52 2 53 2 55 2 57 2 59 2 65 2 66 3 7 3 27 5 14 5 16 5 18 5 26 5 30 5 38 5 48 5 52 5 53 5 55 5 57 5 59 5 65 5 66 6 11 6 12 6 19 6 20 6 25 6 36 6 54 6 56 6 62 6 69 6 77 6 79 6 96 7 47 8 27 10 22 11 13 11 17 11 24 11 29 11 40 11 49 11 68 11 97 1...
result:
ok 571 numbers
Test #11:
score: 5
Accepted
time: 244ms
memory: 14752kb
input:
1000 291640644163858666081098032534898160 227357873561114642640834038516007202 13245561176000847812806783283096383 289847020373306548740443264748943677 289847020373306548740443264748943677 578552671736987388173788537730093157 6996821701676472759359784939297029 121600854669192376466073378531494349 40...
output:
64 4 5 5 14 13 34 14 47 14 249 21 409 32 187 37 93 37 929 40 102 40 146 41 816 46 258 47 597 48 249 50 64 55 83 55 455 61 518 79 125 79 422 84 455 86 170 94 929 103 146 107 718 117 207 126 422 133 222 136 159 136 270 143 310 149 347 160 270 177 946 211 289 212 324 217 832 221 333 247 496 248 368 264...
result:
ok 129 numbers
Test #12:
score: 5
Accepted
time: 243ms
memory: 16100kb
input:
1000 317806128212589382361485435548385354 597207142028658456258290616807422380 282499763987829361735046986098432002 24448882920496661495145116220484493 300550860888796946709885526447080103 33872715256434239525511448119212677 120942718535851021168502782891536521 157753857877561652333091326318512411 1...
output:
67 6 12 9 24 9 118 9 119 15 113 23 53 24 35 25 118 25 119 34 92 38 80 41 133 46 104 46 566 55 62 67 265 67 887 68 151 79 353 102 200 105 566 110 172 111 185 119 119 131 223 153 259 154 819 157 371 183 333 191 239 191 447 191 911 209 661 226 747 227 293 240 447 240 911 248 313 254 456 266 887 285 545...
result:
ok 135 numbers
Test #13:
score: 5
Accepted
time: 240ms
memory: 16112kb
input:
1000 175069690451769261445886256076778193 857377950130838290706851349542703 431074356670154777789431486369543688 246568169661771346881881284912665915 137955738264388301374432966342843643 501622433047900938246400117167545693 506556801796207331983983371075935 458676314832825522220021693067634300 72787...
output:
70 1 16 1 20 1 254 7 36 15 50 17 20 17 254 20 774 21 254 29 92 31 973 33 118 40 40 43 70 47 54 50 241 52 113 61 306 61 411 67 837 81 135 81 386 111 492 112 171 115 206 116 523 118 158 132 514 136 386 137 353 137 565 148 281 164 190 185 218 204 247 216 755 240 316 254 485 257 442 257 636 257 651 261 ...
result:
ok 141 numbers
Test #14:
score: 5
Accepted
time: 258ms
memory: 14540kb
input:
1000 617267984368402121547949873441168308 74192584480760102557741382968162984 423581651907322293415720778192460243 20860154602830400218895069317697272 121752740599378404172232949246702703 8480850023521496288452919096991489 12453086212561936481787210116074927 48248460229948537657399224672895337 65369...
output:
73 1 697 3 22 3 334 4 41 4 69 4 186 5 12 11 90 14 126 14 322 22 532 23 334 25 915 36 61 42 69 42 186 46 156 54 246 56 105 56 116 57 274 57 899 59 266 70 186 78 177 88 799 94 94 97 315 97 317 98 352 101 149 102 579 106 116 110 456 110 549 110 682 127 322 133 135 154 781 158 204 160 160 166 287 173 40...
result:
ok 147 numbers
Test #15:
score: 0
Wrong Answer
time: 355ms
memory: 24476kb
input:
100000 254265166806186183995767664564186160 276525657902692643693464830133973599 14597708679048712471331958616721616 359181801526616841850768359903202650 384064071764377152750283075761763137 167144655873360876803761918905939916 314660320441387223855132017820518857 46234119728759441422159276896429495...
output:
6 128 1340 190 415 211 676 1308 2631 6101 6130 94076 94076
result:
wrong answer 1st numbers differ - expected: '59', found: '6'
Test #16:
score: 0
Wrong Answer
time: 360ms
memory: 22840kb
input:
100000 64877618662819381351327782685017620 287251583192024472245732328155777164 81924196794087694863774077894446261 587898088473307245633470467109625817 63983457055859356681418342070232640 467531606610562532827526302618648017 156643527477744456327114323891851228 410775814992874901613953568756269400 ...
output:
14 40 40 175 850 392 1098 1246 1867 3089 8937 3362 4817 5072 5745 8302 10518 42530 42530 58470 58470 63238 63238 64881 65290 82014 82014 95579 95579
result:
wrong answer 1st numbers differ - expected: '67', found: '14'
Test #17:
score: 0
Wrong Answer
time: 353ms
memory: 24608kb
input:
100000 400382407579164630565570106786834592 598989994019780586622660096767873140 202713125527451525208506091402848040 306656951540312625601017432814883193 385533812806222459233700726433861948 114792968802667943882261595590188390 683453871393149097207519280770515051 6797074249509152378642958893459456...
output:
8 1545 2074 6389 6389 9132 10778 26776 26776 30755 30755 37492 37835 53301 53301 92158 92158
result:
wrong answer 1st numbers differ - expected: '62', found: '8'
Test #18:
score: 0
Wrong Answer
time: 545ms
memory: 35992kb
input:
300000 11979100587810800802923349735474971 384568989741449185758732548398537465 692031101896121489295510142056399609 174419831569051368765733330998938852 72675424159770430711139346222466676 792926893016443498788235028652731500 131899888836396741244415546802600120 449365951867691934494751253423827525...
output:
5 10 21 588 1971 12090 12090 46732 46732 203763 203763
result:
wrong answer 1st numbers differ - expected: '55', found: '5'
Test #19:
score: 0
Wrong Answer
time: 555ms
memory: 36616kb
input:
300000 13159476220540052611063099704777119 404069210783480886299855108899917825 606724469975551403885266994483701254 161478011836648686548748736172102098 191126570380800476556975432074751901 15799586089681007279542308115871748 121959472970612542582013529465554644 289381348752343543671715423172520800...
output:
1 8551 8648
result:
wrong answer 1st numbers differ - expected: '54', found: '1'
Test #20:
score: 0
Wrong Answer
time: 555ms
memory: 36340kb
input:
300000 711310443416742782431396964084452 1303778642379799335236750513539496 1235880107471962090842032248476135 1815830256757580411001511688032056 1646915814259921137430603642187095 2066825075807731605894416184650449 110919427936977169221309066929877 1896880667099287111024124058694220 139227650014149...
output:
4 4397 4492 24647 24647 24770 24770 38778 39517
result:
wrong answer 1st numbers differ - expected: '57', found: '4'