QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#370524 | #5045. King | zzuqy# | WA | 1238ms | 28888kb | C++11 | 2.2kb | 2024-03-29 10:09:05 | 2024-03-29 10:09:05 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
long long read()
{
long long x;scanf("%lld",&x);return x;
}
ll quick(ll a,ll b,ll mod)
{
ll ans=1;
while(b)
{
if(b&1)
ans=ans*a%mod;
b=b/2;
a=a*a%mod;
}
return ans;
}
ll a[200010],n,p;
map<int,int>id;//表示
vector<int>pos[200010];
int ask1()
{
int x=(1ll*rand()*rand()+rand())%n+1;
while(x==n)
x=(1ll*rand()*rand()+rand())%n+1;
int y=x+1;
int q=a[y]*quick(a[x],p-2,p)%p;
ll qq=quick(q,p-2,p);
int len=2;
while(x!=1)//往前跳
{
ll v=id[a[x]*qq%p];
if(v==0||pos[v][0]>=x)
break;
len++;
x=*(lower_bound(pos[v].begin(),pos[v].end(),x)-1);
}
while(y!=n)
{
ll v=id[a[y]*q%p];
if(v==0||pos[v].back()<=y)
break;
len++;
y=*upper_bound(pos[v].begin(),pos[v].end(),y);
}
return len;
}
int ask2()
{
int x=(1ll*rand()*rand()+rand())%n+1;
while(x==n)
x=(1ll*rand()*rand()+rand())%n+1;
int y=min(n,x+2ll);
int q=a[y]*quick(a[x],p-2,p)%p;//
int qq=quick(q,p-2,p);
int len=2;
while(x!=1)//往前跳
{
ll v=id[a[x]*qq%p];
if(v==0||pos[v][0]>=x)
break;
len++;
x=*(lower_bound(pos[v].begin(),pos[v].end(),x)-1);
}
while(y!=n)
{
ll v=id[a[y]*q%p];
if(v==0||pos[v].back()<=y)
break;
len++;
y=*upper_bound(pos[v].begin(),pos[v].end(),y);
}
return len;
}
void work()
{
n=read();p=read();
id.clear();
int sum=0;
for(int i=1;i<=n;i++){
a[i]=read();
}
for(int i=1;i<=n;i++)
{
if(id[a[i]]==0)
{
sum++;
id[a[i]]=sum;
}
pos[id[a[i]]].push_back(i);
}
int ans=-1;
for(int i=1;i<=17;i++){
int t1=ask1(),t2=ask2();
ans=max(ans,max(t1,t2));
}
if(ans*2<n)
ans=-1;
cout<<ans<<'\n';
for(int i=1;i<=sum;i++)
pos[i].clear();
}
signed main()
{
srand(time(0));
for(int t=read();t;t--)
work();
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 9420kb
input:
4 6 1000000007 1 1 2 4 8 16 6 1000000007 597337906 816043578 617563954 668607211 89163513 464203601 5 1000000007 2 4 5 6 8 5 1000000007 2 4 5 6 7
output:
5 -1 3 -1
result:
ok 4 number(s): "5 -1 3 -1"
Test #2:
score: 0
Accepted
time: 115ms
memory: 8540kb
input:
1000 200 495189361 193302375 262009153 248101278 250233641 303504256 426913173 23261177 206011896 214770731 286184509 492688635 207979481 282629026 450810670 41818047 359796006 445343921 241742611 249404909 41291916 392252331 125287519 92825425 162555413 371172157 420486666 270651384 309213995 11709...
output:
-1 133 -1 187 163 114 114 132 100 108 116 137 115 -1 165 115 142 165 -1 -1 108 129 -1 144 122 -1 111 146 190 159 134 -1 117 180 196 -1 -1 192 123 110 -1 106 153 103 -1 -1 103 169 -1 174 152 -1 181 113 135 -1 153 199 182 -1 177 152 177 162 -1 115 -1 -1 -1 113 128 -1 -1 -1 -1 168 167 -1 140 -1 -1 -1 1...
result:
ok 1000 numbers
Test #3:
score: 0
Accepted
time: 116ms
memory: 8436kb
input:
1000 200 949663931 479217281 320985989 765005251 6434894 250659962 96381980 929176627 859155083 837781618 895381960 276913403 206799800 594561194 451400141 287326771 230131436 499694353 149062037 769076212 249680039 876506380 680573243 672238085 235553233 593493391 524937617 832401231 490042272 4494...
output:
198 -1 -1 -1 120 -1 162 -1 101 -1 103 157 188 -1 -1 177 -1 126 114 -1 177 -1 -1 150 -1 148 140 165 -1 102 -1 192 -1 -1 -1 181 149 196 -1 -1 173 147 -1 149 -1 -1 200 -1 -1 -1 -1 -1 156 -1 114 119 199 127 123 138 169 188 146 -1 137 -1 -1 -1 121 -1 -1 121 -1 -1 -1 108 117 127 -1 127 194 -1 121 -1 -1 12...
result:
ok 1000 numbers
Test #4:
score: 0
Accepted
time: 112ms
memory: 8380kb
input:
1000 200 752331551 23573436 686888652 118880475 606109605 504896777 156156511 407092389 168008046 588489051 384747939 312334251 10179640 389706827 496937297 625716990 602916042 580060754 535624296 196865310 693079720 672788885 104900220 416739470 142969723 655913476 432092835 454858443 698545241 763...
output:
-1 179 -1 -1 126 -1 189 -1 115 -1 -1 -1 175 -1 109 -1 166 190 129 -1 -1 108 -1 135 -1 174 109 -1 183 -1 -1 -1 142 -1 105 159 163 144 -1 -1 -1 124 175 135 183 132 -1 -1 115 -1 -1 130 159 -1 -1 160 138 145 196 -1 123 163 -1 -1 181 -1 137 126 111 -1 -1 110 111 148 -1 -1 131 -1 -1 -1 101 -1 -1 -1 -1 -1 ...
result:
ok 1000 numbers
Test #5:
score: 0
Accepted
time: 117ms
memory: 8580kb
input:
1000 200 952479163 404962930 635613728 875512822 126836765 893278336 93755885 802367656 41132902 703323879 109154481 793288802 49973196 534490899 462994291 829278242 789093683 134072789 384627711 513380294 28212590 922131395 333371011 352605762 351655730 28129292 473972568 10559174 951685030 7877219...
output:
-1 -1 -1 171 -1 190 -1 -1 -1 107 -1 -1 176 -1 -1 118 -1 -1 119 -1 -1 160 -1 100 -1 -1 129 190 165 -1 -1 108 -1 -1 -1 188 167 121 189 190 113 153 -1 -1 -1 -1 142 192 186 102 108 -1 -1 -1 -1 -1 137 160 143 146 163 156 163 176 135 -1 -1 -1 -1 -1 -1 -1 -1 117 -1 -1 -1 147 166 -1 200 195 189 177 -1 143 -...
result:
ok 1000 numbers
Test #6:
score: 0
Accepted
time: 153ms
memory: 8728kb
input:
100 2000 146158349 19643059 687117 30976705 141997757 126939439 27291348 99640815 77869374 140943896 108863607 47555226 24332054 20814180 9774186 95917237 54599801 123926643 144812251 18602850 105663323 135089587 86540799 102680207 83257587 98590031 102391932 51059987 8865754 980981 32147720 8025236...
output:
-1 -1 1976 -1 1443 -1 1206 1958 -1 1973 -1 -1 1294 -1 -1 -1 1223 -1 1457 1496 1860 1473 -1 -1 -1 -1 1654 -1 -1 -1 1505 1306 -1 -1 1696 -1 -1 -1 1475 1133 1189 1609 -1 -1 1397 1540 -1 1625 1191 -1 1923 -1 1835 -1 1296 -1 -1 -1 -1 1893 1705 1378 1343 -1 -1 1444 -1 -1 -1 1788 -1 1255 -1 -1 -1 -1 -1 -1 ...
result:
ok 100 numbers
Test #7:
score: 0
Accepted
time: 170ms
memory: 8640kb
input:
100 2000 275587717 83150209 104356116 34298444 197772460 101494007 261547554 223901747 141042340 131644199 60357915 86344257 81799664 202980147 152575387 115211945 7568397 260000358 100079566 95526927 11929407 165620994 44220242 62535336 42656523 39073826 149365602 253784018 119905129 214185578 2576...
output:
-1 1379 -1 -1 -1 1294 1717 -1 1569 1573 1375 -1 -1 1151 1859 1927 -1 1953 -1 1655 -1 -1 1986 -1 1019 -1 -1 1791 -1 1641 1783 1092 1488 1364 -1 1640 1875 1080 -1 1860 -1 1509 1578 -1 -1 1303 -1 1783 -1 -1 1744 1727 1525 -1 -1 1462 -1 -1 -1 -1 1316 1389 1144 -1 -1 1361 -1 1866 1334 -1 1313 1792 1286 -...
result:
ok 100 numbers
Test #8:
score: 0
Accepted
time: 149ms
memory: 8532kb
input:
100 2000 728295619 196905643 523233418 352318827 369770119 347085435 127560509 546671396 362387446 649410690 156802530 298823172 508289744 452232923 497191988 294603059 371099463 359230006 112535834 365805832 66877149 503870773 709803811 404046859 570062640 574727791 550224131 433734296 17881765 652...
output:
1982 -1 1859 1702 -1 1998 1377 -1 1731 1754 1498 1079 -1 1329 1879 -1 1334 -1 -1 1105 -1 -1 -1 1756 1165 -1 -1 -1 1328 -1 -1 1307 1815 -1 1666 1159 1263 -1 -1 -1 -1 -1 1443 -1 -1 1796 -1 1122 1310 1183 -1 -1 -1 -1 -1 1687 1122 1906 1200 -1 -1 1899 1543 -1 1487 -1 -1 -1 1885 1263 1325 -1 -1 1164 1548...
result:
ok 100 numbers
Test #9:
score: 0
Accepted
time: 166ms
memory: 8576kb
input:
100 2000 933493147 311022270 68427073 410339431 66474535 75931530 216168461 596520713 772600691 587660302 307741208 399247506 406645429 62857626 3532644 485034914 95405783 290695394 802486951 113550555 678338176 331200438 608959909 689318946 20753772 157370341 699828644 477646090 360131489 626962275...
output:
-1 1314 -1 -1 -1 1309 -1 1693 -1 1491 1438 -1 1012 1591 -1 -1 -1 1008 1917 1829 -1 1580 -1 1904 -1 1903 1155 1509 1378 1328 1050 -1 1576 -1 1752 1469 1858 -1 1261 -1 -1 1951 -1 1563 -1 1317 -1 1502 1867 -1 -1 1623 -1 -1 -1 1956 -1 -1 1215 1619 -1 -1 1852 1957 1561 -1 1493 -1 -1 1649 1110 1484 1429 1...
result:
ok 100 numbers
Test #10:
score: 0
Accepted
time: 268ms
memory: 10440kb
input:
10 20000 394172071 215340230 130633568 345392055 252111757 290095347 168672848 194628253 178431552 4977718 99966452 268841997 280806854 303621488 25038073 104682112 315461954 307022385 171592359 96110115 293022137 333987173 216781089 336833348 28521180 90994503 276664376 261103859 334641831 14856855...
output:
19880 -1 -1 13636 14129 -1 13865 -1 -1 -1
result:
ok 10 numbers
Test #11:
score: 0
Accepted
time: 251ms
memory: 10472kb
input:
10 20000 831500497 756984954 294988881 429721584 295799143 257217177 50456012 13420397 2969434 721431867 225933624 119351587 523441 211421177 294967820 42091607 225669354 190586927 101257586 45651368 244907097 778123162 44054039 684914480 764858903 102131788 351954286 780877035 439837711 428415753 7...
output:
-1 -1 -1 15494 14393 14874 -1 -1 -1 -1
result:
ok 10 numbers
Test #12:
score: 0
Accepted
time: 202ms
memory: 10536kb
input:
10 20000 905983279 751785219 756502769 317100935 46106015 81697243 113450190 218531390 732183548 337309810 77491620 16286634 236726435 305167458 104295335 503145608 404379366 171869896 258486011 272629763 713887214 873622033 534736735 24120356 224608505 36553224 379385885 317448347 393152738 8866108...
output:
-1 -1 -1 -1 -1 12977 13633 -1 14693 10329
result:
ok 10 numbers
Test #13:
score: 0
Accepted
time: 357ms
memory: 10396kb
input:
10 20000 144511651 123896984 53764446 105306768 103158669 35196311 130674500 83966631 5993612 80522785 141568416 27425680 35528114 133382 99203681 76234496 93249763 140627841 75825332 58193203 100605893 10297744 81443846 38431311 134426404 32085087 33126697 128392840 35165175 81204390 69243064 93196...
output:
16666 17656 -1 -1 -1 -1 14609 17394 18594 13681
result:
ok 10 numbers
Test #14:
score: 0
Accepted
time: 782ms
memory: 28888kb
input:
1 200000 503181461 107429481 294405700 206565826 495988566 37179765 6546199 110332231 437691313 274385052 421520839 85026366 327233500 143699080 63667028 327938631 27533615 355276066 487285084 407716484 302709200 376088216 363588280 378116327 196388430 357959260 412581280 391371092 422167063 3623876...
output:
118278
result:
ok 1 number(s): "118278"
Test #15:
score: 0
Accepted
time: 993ms
memory: 28816kb
input:
1 200000 675454867 380042934 556489164 434552374 495189650 369846868 6899165 654717118 562979032 544560057 236120079 673341859 340171590 626783457 137792322 605431841 197948736 156566705 177828951 135991396 96059783 457411474 584395061 6813347 75601485 218667838 124496749 494264789 71692566 28824401...
output:
142643
result:
ok 1 number(s): "142643"
Test #16:
score: 0
Accepted
time: 1238ms
memory: 28724kb
input:
1 200000 60324409 51939046 34252820 22461608 29712161 36420311 1147508 32901308 15512233 23334023 35546542 24026620 12210103 53562137 57393256 53634724 3364064 32749246 18441242 1105447 30360481 26761245 41588892 26340436 29909011 51311120 28810668 60004026 10533810 18870790 48746108 44671535 159779...
output:
174335
result:
ok 1 number(s): "174335"
Test #17:
score: 0
Accepted
time: 147ms
memory: 28760kb
input:
1 200000 392960111 181739746 47157565 269347140 65403397 304536088 298245479 330308437 76917091 342532299 273626156 373104074 344820389 241641115 93082829 252043316 189605772 302523233 335962472 31078204 294740895 152851882 207902532 392581791 336280905 7206845 136439293 97424930 348175420 4408133 2...
output:
-1
result:
ok 1 number(s): "-1"
Test #18:
score: 0
Accepted
time: 383ms
memory: 19876kb
input:
1 200000 50665379 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 ...
output:
100000
result:
ok 1 number(s): "100000"
Test #19:
score: 0
Accepted
time: 484ms
memory: 19884kb
input:
1 200000 50665379 22623774 11311887 30988633 40827006 20413503 35539441 43102410 21551205 36108292 18054146 9027073 29846226 14923113 32794246 16397123 33531251 42098315 46381847 48523613 49594496 24797248 12398624 6199312 3099656 1549828 774914 387457 25526418 12763209 31714294 15857147 33261263 41...
output:
100000
result:
ok 1 number(s): "100000"
Test #20:
score: 0
Accepted
time: 483ms
memory: 19296kb
input:
1 200000 281130937 1 4 1 8 1 16 1 32 1 64 1 128 1 256 1 512 1 1024 1 2048 1 4096 1 8192 1 16384 1 32768 1 65536 1 131072 1 262144 1 524288 1 1048576 1 2097152 1 4194304 1 8388608 1 16777216 1 33554432 1 67108864 1 134217728 1 268435456 1 255739975 1 230349013 1 179567089 1 78003241 1 156006482 1 308...
output:
100000
result:
ok 1 number(s): "100000"
Test #21:
score: 0
Accepted
time: 495ms
memory: 19632kb
input:
1 200000 738636427 296556719 517596573 628116500 314058250 157029125 447832776 223916388 111958194 55979097 397307762 198653881 468645154 234322577 486479502 243239751 490938089 614787258 307393629 523015028 261507514 130753757 434695092 217347546 108673773 423655100 211827550 105913775 422275101 58...
output:
100000
result:
ok 1 number(s): "100000"
Test #22:
score: 0
Accepted
time: 15ms
memory: 9252kb
input:
1000 2 276978727 260010368 88304478 2 158375449 14007988 42989300 2 265300493 246056707 103672550 2 655511903 430899266 598480001 2 142319921 17136621 100435246 2 457902673 399617359 355188497 2 616379809 417835125 438666049 2 216350689 179035115 102785289 2 886654259 488302044 105632997 2 156729619...
output:
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...
result:
ok 1000 numbers
Test #23:
score: 0
Accepted
time: 16ms
memory: 8560kb
input:
1000 4 172781461 150015400 65108653 50648570 10693060 3 604213499 437376898 222624492 558168969 3 405284227 193074404 91587221 353249967 3 566230397 157548757 62762058 466670214 5 363988607 28650347 173788117 104668203 351804479 116840170 5 559821553 155614238 227458796 4497874 59881986 116064362 4 ...
output:
4 2 2 2 -1 -1 3 2 3 2 3 2 -1 2 2 2 2 4 2 5 4 4 4 2 2 2 -1 3 2 2 2 3 2 2 3 2 2 4 2 2 3 2 2 4 2 2 2 2 3 2 5 3 2 2 2 2 2 3 3 2 -1 2 4 5 3 -1 2 -1 -1 -1 2 2 2 -1 2 -1 4 2 3 2 2 2 3 2 3 2 2 2 2 2 2 2 3 2 -1 2 -1 3 3 3 2 -1 2 3 2 2 2 2 3 3 4 4 2 3 5 3 3 -1 2 2 3 -1 5 2 4 2 2 2 3 5 2 -1 3 2 2 3 5 2 2 4 2 3...
result:
ok 1000 numbers
Test #24:
score: 0
Accepted
time: 19ms
memory: 8420kb
input:
1000 2 536585177 99038749 97516014 6 931710817 116137533 795339380 931363320 895475086 868081293 902189276 4 352662481 320313427 171128238 240243123 321888266 3 343322653 337769782 325422317 155123432 8 551127179 435583987 154184412 26763291 157730106 467081434 214177989 376752621 102242465 2 750439...
output:
2 -1 2 2 5 2 5 8 2 4 4 3 2 -1 7 2 -1 2 2 -1 6 3 5 -1 5 -1 2 5 2 4 -1 -1 -1 -1 3 5 2 -1 -1 -1 5 3 -1 -1 5 -1 -1 -1 7 -1 2 6 7 9 -1 7 5 5 -1 -1 3 2 4 4 2 5 3 2 -1 2 -1 3 -1 2 2 5 4 2 2 5 4 7 2 7 2 4 -1 3 10 10 -1 2 -1 -1 2 2 6 5 -1 9 7 -1 -1 2 6 2 7 -1 4 2 5 2 3 7 7 2 -1 4 5 2 9 3 8 8 3 6 6 6 4 5 -1 4...
result:
ok 1000 numbers
Test #25:
score: -100
Wrong Answer
time: 18ms
memory: 8440kb
input:
1000 6 983520137 4073771 936439870 628012444 725494051 694294122 726397428 3 600298301 516252993 206871719 106594570 5 843185383 409739584 58706225 264392272 789765489 358945083 2 317735753 40369446 118618621 9 994603937 321579439 666019853 584042329 233744403 596554056 932175802 574951405 567652445...
output:
6 2 -1 2 6 6 2 5 3 2 3 2 2 4 2 2 9 5 9 5 2 8 6 -1 2 2 5 4 -1 5 3 -1 2 4 -1 8 -1 7 -1 4 5 6 3 -1 5 -1 6 5 4 2 2 4 2 -1 2 6 -1 3 -1 -1 2 -1 5 -1 5 2 2 5 2 -1 4 2 9 6 2 5 2 -1 2 -1 2 -1 -1 -1 3 -1 2 8 5 -1 2 -1 3 4 4 5 -1 -1 5 3 -1 -1 3 4 6 8 -1 2 5 3 8 6 2 -1 2 -1 3 5 2 5 2 3 5 5 6 -1 2 2 2 2 -1 6 6 2...
result:
wrong answer 282nd numbers differ - expected: '3', found: '-1'