QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#21385 | #2825. 大碗宽面 | DaBenZhongXiaSongKuaiDi# | AC ✓ | 1780ms | 325772kb | C++17 | 2.5kb | 2022-03-04 17:58:25 | 2022-05-08 02:58:31 |
Judging History
answer
#include <bits/stdc++.h>
#pragma GCC optimize(3)
using namespace std;
typedef long long ll;
const int maxn=(int)1e4+5,maxc=505,dif=500,B=65536;
int n,k,tot,cnt[maxn],t[maxn][maxc],id[maxn*maxc],ori[maxn*maxc];
struct Node{int val;int x,y;bool operator < (const Node&t) const {return val<t.val;}}rec[maxn*maxc];
vector<Node> X[B],Y[B]; int szx[B],szy[B];
int st[maxc<<1],pre[maxc<<1][maxn],nxt[maxc<<1][maxn],val[maxn],ans[maxn];
inline void modify(int v,int v_,int x) {for(int u=st[v];u;u=nxt[v][u]) ans[u]^=(u+x),ans[v_]^=(u+x);}
inline void add(int v,int x) {nxt[v][x]=st[v],pre[v][st[v]]=x,st[v]=x;}
inline void del(int v,int x)
{
if(st[v]==x) st[v]=nxt[v][x];
pre[v][nxt[v][x]]=pre[v][x],nxt[v][pre[v][x]]=nxt[v][x];
}
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read(int&x) {
char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
return x;
}
void bsort(){
for(int al=1;al<=k;al++){
int now=rec[al].val^((rec[al].val>>16)<<16);
++szx[now];
now=rec[al].val>>16;
++szy[now];
}
for(int al=0;al<B;al++) X[al].resize(szx[al]),Y[al].resize(szy[al]),szx[al]=szy[al]=0;
for(int al=1;al<=k;al++){
int now=rec[al].val^((rec[al].val>>16)<<16);
X[now][szx[now]++]=rec[al];
}
for(int al=0;al<B;al++)for(int be=0,l=X[al].size();be<l;be++){
int now=X[al][be].val>>16;
Y[now][szy[now]++]=X[al][be];
}
int pos=0;
for(int al=0;al<B;al++)for(int be=0;be<szy[al];be++)
rec[++pos]=Y[al][be];
}
int main(){
// freopen("test.in","r",stdin);
// freopen("test.out","w",stdout);
read(n);
for(int al=1;al<=n;al++){
read(cnt[al]);
for(int be=1;be<=cnt[al];be++)
read(t[al][be]),rec[++k]=(Node){t[al][be],al,be};
}
tot=k; bsort();
for(int al=1;al<=tot;al++) ori[al]=rec[al].val;
for(int al=1;al<=tot;al++)
t[rec[al].x][rec[al].y]=al,
id[al]=rec[al].x;
// for(int al=1;al<=k;al++) printf("_%d_ ",recc[al])
// printf("%.4lf\n",clock()/1000.0);
for(int al=1;al<=n;al++) val[al]=cnt[al],add(val[al]+dif,al);
for(int al=1;al<=tot;al++){
int now=id[al]; del(val[now]+dif,now); val[now]-=2;
modify(-val[now]+dif,now,ori[al]+now),modify(-val[now]-1+dif,now,ori[al]+now);
add(val[now]+dif,now);
}
for(int al=1;al<=n;al++) sort(t[al]+1,t[al]+cnt[al]+1),ans[al]^=(al*2+ori[t[al][(cnt[al]+1)/2]]);
for(int al=1;al<=n;al++) printf("%d\n",ans[al]);
return 0;
}
/*
3
3 1 2 3
3 3 4 5
2 4 2
*/
详细
Test #1:
score: 100
Accepted
time: 1186ms
memory: 290560kb
input:
10000 500 859366524 799639632 478076363 151604321 607428939 233690027 688301763 751626556 522306660 536984621 678633141 10578133 793244142 296437947 543452728 219588017 242235086 875832010 439306786 621619872 896296190 855348805 322308598 264128973 159679782 141772327 531429282 34093406 776807465 22...
output:
1067427185 39974308 1013395314 92517059 34948556 954314749 1019304725 81852217 14309044 54130846 35792652 1034202845 93901788 1032937383 98299641 71419938 70902930 976383972 1031643060 1010313104 1006450452 28189852 86943269 46288302 998291304 83807081 1027308959 23261403 995953387 1000623412 426439...
result:
ok 10000 lines
Test #2:
score: 0
Accepted
time: 1398ms
memory: 325772kb
input:
10000 500 798254894 598183457 188492366 213343500 144024969 207571951 470634101 33909699 797976261 987433900 965740329 414192594 225990846 16409557 927106922 121246302 126239507 124080119 621042082 842641728 725791146 297984743 849070111 813339625 962031535 552579090 667865219 190108719 612404865 83...
output:
941842913 76756424 984265872 91718581 46075887 83617387 100143500 61029346 1029115789 1072666963 125695997 109138178 25122426 74481547 7392266 1042520568 973853031 12969101 73891891 73600185 1073702433 1038100420 93881633 995390588 31169406 126128916 35152535 131551860 50231694 975673455 976894787 6...
result:
ok 10000 lines
Test #3:
score: 0
Accepted
time: 674ms
memory: 272056kb
input:
10000 500 1 1 0 0 1 1 1 0 0 0 0 0 1 1 0 1 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 0 1 1 0 1 0 0 0 1 1 1 1 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 0 1 1 0 1 1 0 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 1 0 0 1 0 0 1 0 1 1 1 1 1 0 0 0 1 1 1 1 0 1 1 1 0 1 1 0 1 1 0 0 1 0 ...
output:
3793 168 1026 7361 111 7924 5675 14936 33 9130 721 6977 8662 9029 208 10028 23 10209 10077 14294 6087 962 368 11966 7237 1227 4246 8886 10066 14996 16062 295 11931 573 14239 14120 14026 9984 1798 9952 1329 8249 1535 9076 8813 6068 11687 15534 10029 667 800 3135 15469 8290 13559 9688 15157 358 391 43...
result:
ok 10000 lines
Test #4:
score: 0
Accepted
time: 1780ms
memory: 325092kb
input:
10000 499 336877261 26362245 973593660 767344833 254149914 924437975 7702640 208740280 983230139 158667687 4663145 114489254 887987788 24594914 936420052 213343501 126344736 883392030 4523436 284383841 828950796 511521744 59140803 156289177 44906199 992436310 247903279 395981697 987433901 425899815 ...
output:
807486028 891293819 261741040 469550235 438622955 502240134 1020170815 786155514 200012834 300923795 97956218 216773482 461746241 295598620 431574498 467873694 202922246 21578115 383502596 413057482 810175322 112838736 246729133 362626304 675427139 37113891 967219300 231354476 900969847 231684200 26...
result:
ok 10000 lines
Test #5:
score: 0
Accepted
time: 1668ms
memory: 325108kb
input:
10000 499 794283717 121003282 798084749 890678492 1351179 937533223 34093407 934931895 76872698 307784 33517122 905434213 91907566 164929402 872918843 824856622 102663700 106274628 923185661 486582427 98427856 950253378 47165093 998051999 170889435 981409462 833284370 10578134 3697214 114527674 7706...
output:
1055931898 477296557 463136746 680402397 536394216 829787301 221056371 49324134 704670552 65906308 127225518 485464935 1030017247 157167505 834023362 90265654 547009735 930699678 965939751 351800808 157347030 856741179 216897925 824828071 11807304 101078913 815907707 809897987 857154999 5833218 2245...
result:
ok 10000 lines
Test #6:
score: 0
Accepted
time: 862ms
memory: 324036kb
input:
10000 500 999999961 999999941 999999927 999999573 999999985 999999620 999999529 999999979 999999938 999999929 999999615 999999870 999999832 999999874 999999632 999999749 999999941 999999751 999999659 999999698 999999722 999999643 999999519 999999672 999999841 999999508 999999820 999999597 999999717 ...
output:
11068 7895 15171 14094 12800 6461 4911 10202 4381 3251 11004 16380 8287 4311 7791 9388 14469 12331 7494 2356 3227 1819 158 13646 1420 12682 12679 12901 39 1204 4444 12766 11281 13520 6955 14501 4428 32 4957 11644 174 8653 6420 11724 4698 948 1716 4087 3601 1397 14080 884 14872 12418 10330 10218 1176...
result:
ok 10000 lines
Test #7:
score: 0
Accepted
time: 779ms
memory: 288856kb
input:
10000 500 999999908 999999972 999999977 999999619 999999866 999999552 999999834 999999951 999999881 999999565 999999695 999999967 999999560 999999564 999999641 999999912 999999738 999999597 999999987 999999834 999999777 999999523 999999949 999999920 999999655 999999813 999999843 999999984 999999707 ...
output:
13877 7472 14720 16279 15657 14138 4982 4966 13249 672 13220 6976 14775 3541 1766 11951 7683 8644 6073 2361 7393 12340 815 5106 9350 5714 3069 15117 15521 15470 11381 11286 12965 12233 7423 14408 11609 6315 7730 11906 12910 5362 4154 11058 8595 4507 652 5177 2539 624 9792 11170 10312 353 13677 6130 ...
result:
ok 10000 lines
Test #8:
score: 0
Accepted
time: 34ms
memory: 23456kb
input:
5000 2 0 0 2 0 0 2 0 1 1 0 1 1 2 0 1 2 1 1 2 1 0 1 0 1 0 2 1 0 2 0 1 2 0 1 2 1 0 1 0 2 0 0 1 1 2 1 1 1 1 1 1 2 1 1 2 0 1 1 0 1 1 1 1 2 0 1 1 0 1 0 1 1 1 1 2 1 1 1 0 1 1 1 1 1 0 2 1 1 1 1 1 0 1 1 2 0 0 1 1 1 1 2 1 0 1 0 1 0 1 0 2 0 0 2 1 1 2 1 0 1 1 2 0 1 2 0 1 1 0 1 1 2 1 0 2 0 0 1 0 1 0 1 1 2 0 1 1...
output:
0 5000 6342 4742 3014 4586 2913 5550 1630 4794 6918 630 1130 3674 178 5000 2638 623 314 6662 4897 7402 4210 2158 2622 5482 306 5094 4038 5826 4705 5086 4558 5362 178 7203 6214 4986 4362 5016 3358 7122 1286 4326 3110 4458 0 8131 7626 4242 1222 6998 678 290 2318 5112 2494 3290 7850 7574 3654 6458 7314...
result:
ok 5000 lines