QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#21385#2825. 大碗宽面DaBenZhongXiaSongKuaiDi#AC ✓1780ms325772kbC++172.5kb2022-03-04 17:58:252022-05-08 02:58:31

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-08 02:58:31]
  • 评测
  • 测评结果:AC
  • 用时:1780ms
  • 内存:325772kb
  • [2022-03-04 17:58:25]
  • 提交

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