QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#302079#15. 虫逢Unknown150820 317ms65428kbC++201.4kb2024-01-10 16:04:032024-01-10 16:04:04

Judging History

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

  • [2024-01-10 16:04:04]
  • 评测
  • 测评结果:20
  • 用时:317ms
  • 内存:65428kb
  • [2024-01-10 16:04:03]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

void main_program();

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	main_program();
}

int n, M, L;
string s;
vector<vector<int>> v;

vector<int> mapping;

void create_mapping(){
	mapping.assign(256, 0);
	int crr = 0;
	for (char c = 'a'; c <= 'z'; c++) mapping[c] = crr++;
	for (char c = 'A'; c <= 'Z'; c++) mapping[c] = crr++;
	for (char c = '0'; c <= '9'; c++) mapping[c] = crr++;
	for (char c: "~!@#$%^&()[]`:;\"'<>,.?/|\\=-{}") mapping[c] = crr++;
}

void main_program(){
	cin >> n >> M >> L;
	cin >> s;

	create_mapping();

	v.assign(n * 2, vector<int>(n * 2));
	map<int, vector<int>> mp;

	for (int i = 0; i < n * 2; i++){
		for (int j = 0; j < L; j++){
			int H = 0;
			for (int k = 0; k < 4; k++){
				H = H * 92 + mapping[s[i * L * 4 + j * 4 + k]];
			}
			mp[H].push_back(i);
		}
	}

	vector<map<int, int>> connections(n * 2);
	for (auto [gene, lst]: mp){
		for (int i = 0; i < (int)lst.size(); i++){
			for (int j = i+1; j < (int)lst.size(); j++){
				connections[lst[i]][lst[j]]++;
			}
		}
	}

	vector<int> answer(n * 2, -1);
	for (int i = 0; i < n * 2; i++){
		if (answer[i] >= 0) continue;
		for (auto [j, cnt]: connections[i]){
			if (answer[j] >= 0) continue;
			if (cnt >= L/2){
				answer[i] = j; answer[j] = i;
				break;
			}
		}
	}

	for (int i = 0; i < n * 2; i++) cout << answer[i] + 1 << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10
Accepted
time: 36ms
memory: 15696kb

input:

400 400 20
EEg-$7z}ic&Oy(3A7Xhghr!`G"?jPI/cj`BU]dh,35/x:OScim>vk+dwo|((KOM(L_~o#^G5cnL:fC>_#2k1%apE-Q98T-w,8T?w{7Zfk+dwNzj&yAT#M4fSdw#M}??kcY"J]O@TcxT<Mms0h&XIUIK9cnL:K`BVH_-@pXpzL,&i_d^>\*I\k+dwL5vaN`'.Z72Tbb~x^"bLKqV-'u:a4yXn=yW.U/88HNbq&\Y{K&q'a<|8<7j(yc8NVS[2';"N7Xhg?skmC(D"j`BU:G_]Fu[&n'p;($#%~...

output:

39
745
694
66
344
748
379
678
458
596
600
442
323
508
662
435
682
77
32
572
373
527
605
614
616
48
84
444
343
529
242
19
287
632
599
791
421
116
1
258
657
659
625
602
252
181
642
26
510
53
419
140
50
681
184
549
609
453
606
710
730
439
289
232
668
4
464
246
176
477
125
522
384
509
771
279
18
772
112...

result:

ok 800 lines

Test #2:

score: 10
Accepted
time: 317ms
memory: 65428kb

input:

900 900 30
<$`st_N'e{wTJ!fn%0SA3RJTqP0_Z-H;HA%\\sJNRAV1'[[email protected]_Bpl|u1z6_J5w%,h/q/w^wM;_%MSX+T16EQK&h?Q>fn(vCT@{[`II-ExNxGV+pg"QcN)}!K({'Vq#N&--'^6$;yt^\A\+3cBs*algVZXS<$nEY5MQ*z[@^GDjN#a_Bpe,0Fxi,{?<5HN;-A':No>MaXQOR)SVWJ8u<ioF3|@C$oOmDaTY}hFcOjS95H0{ZC3?MucIq[g[Ttgnx};NZA~-v;MTt3CAg@a[='k^;eTCytI...

output:

183
982
516
1419
408
1516
557
567
923
999
358
432
1662
980
466
774
731
281
91
1343
1321
1684
963
1093
702
1198
1170
1094
1590
1349
289
1100
503
501
1362
606
1451
967
993
997
446
1183
826
1620
1697
116
1247
198
1098
817
1524
242
1151
83
311
248
1377
1570
1618
854
674
723
1361
172
1595
1471
984
431
84...

result:

ok 1800 lines

Test #3:

score: 0
Time Limit Exceeded

input:

1600 1600 40
hsoY4eoY'F,2m06W;)%5}R`:uY5F}Ij?bOw%2^tin}q=p3hf$d]$'s2lCBvo!(e>b1TfN)*)rHlV({x)xIU@~GcPym02ZU6BAmnlpWO|'vUHx~XBk#`MLETV/3H#A'"RsdX7Q1B`]Ej4yqft}Ltr?mMtFj_P$NV1)%2o[R>RLY47i*JX5MpiCf#VP7pSv!QdD+^JF%L{[>xQ?EdFG=Tq}_]Vq6mzM'B#Tlq*!eij3Lbt%aA>qC`XV$gMP=((^)XV-D5"/VAn$a/?}bo5]Ej4Ar^4}yB"9_9...

output:


result:


Test #4:

score: 0
Time Limit Exceeded

input:

2500 2500 50
v*+m#?q}Hrg+;H(=ho/Y_DxiGs(B$R|v^$$s)o!p3OGjaI~1\d[f2ZV(E-mXvVOHr(*w5Yl#S7}yYQ[f_lL--:2("W=}2Af`a;cBVIAR(1n|zP@"Pi&,=pR{i2V\sbYR2@[8{X2x-F]o.x=5S7l5e,.3O`?:M]Y25gLF'&o0`c+]$#0|B9]YH!TG}{U=Y[W]r^!6HQ=@r%w3U2-.Jzy$Fz|rv#BVKP)&8'rGDlf=Sv'&0!xPw_=ZR@)l.:*n5w/!R7)eE$9fqeT2Vhe2I6_xm;/pk,.+%^_...

output:


result:


Test #5:

score: 0
Time Limit Exceeded

input:

3600 3600 60
k,i{Q4?)4lEg^l;M-spz5V7G+!+1H~TB!BUPjMuK"hr`>6UFEiX(W4WP)Qq-KdghsXw@*Uw)a3#39qnUxz2H6!7'8A0eTx8$wB|5kVw8-chn1azM`6Ih$m[^pQx=]P4d8$G!5n7+RN|5.Q.Rw`gz5PHG.OhmNbsl&L%8`~I;3+?AFUaIUMbOy)wJU\}hT$;gBFRR/*b#%/*VlDY#28B+/#&{CA0<6JkC-)qQyUg0kEl)//n^$`=a37Ab}nSZ\z/0-,d0s`9<6BeaI`1j<_Nn$([,*UU<DIH...

output:


result:


Test #6:

score: 0
Time Limit Exceeded

input:

6400 6400 80
#pYpSE)bn,eSQc3x;7~=8F3vk'sG;Jgzv"JPka&PmF(o'!Q,_3%?G"L.l#)^_r^"[F=SS()UDLq;{1c%Lt~U/7c>%-Mr[S=RD'MHE}<VTe`}r{&I4`%dcT*AAdSD)RBdrkX^tpdp|[hz&qX1Ts$5$gOS4}s]<Io^M2CYbCy^$46"z0,|&qq:%G>oI"%|?nT[E5,cq+C58?qz|z^KN~UNt0p(#XaAj$fc`?p6D_/eaSnFj&I))L@q/S.M{84wB^}ti]:Bh".Kg)$Yey%/uZ\3$hoKx5IS/4'...

output:


result:


Test #7:

score: 0
Time Limit Exceeded

input:

10000 10000 100
!`Z+4~yp--uU9|2_g`@{b5M;F>A$NwzlnP8}+!UA!>KV5DJz:S@x<TQW{v.HyZ'6[.!O*s6+W8^X+T^A$m7]&Ge!0PbFKAG$hQZ++nl3/\49}CcccH=Rpl,7-0kTd6m!-=Oj=]D~f\OWiy?Dtt]D#~Aq1b(J6.7l(Z#xwF_e*B#Nh|`,<N3xNq)d8**nMTBTCXM9#{y.^H$jSVsV6Sm"YqC}SODAmT8YpaAHFcd/&l[crSYPav{Q0T3F6M1&{auL!>D]%-?6Rk=j&Z\%SX]2,0EW`&U]...

output:


result:


Test #8:

score: 0
Time Limit Exceeded

input:

12100 12100 110
jNb#M3`q7hFKE*".Lp>.Rl"ggiB|~p0|3h_4^g;|1/:vpCJJAz_\#fBJh6oh9q7w(tJbE31v+t`1t:(bvexrJCS>Dsdyv_`2}{>a9v:.<&XNOa]LTu#=z%c*z)3JEGd3TTTgP$tk]Prf6Hb/1eG6:6e.Bl2!nHJ2<Ja),]S1PBc'$"9tjO2/avMUpfG|q2v[`pl=Nq>cM[RVDOw_M:Ztk~[bH]ZC+T**5DQmv]R>W)U>0T8eMW$-.bCLg}E92I)qFa{slC"J]@CU#<3_^#w'tU>]#`5~...

output:


result:


Test #9:

score: 0
Time Limit Exceeded

input:

14400 14400 120
x]kNS_WN&Y>tRD|@!:V|<HKIp4f[0`=8[l5)a%h&S_/0rTs^rs,)#f5y>p~HXpytf9TR6!~)4jJ-5VSy-_yOJS&V@^Cf>r5O5IeI?p;9OZ%J.G<aHr2-5ioks9@w(x8KWlh161zDot+S8TP%R,*x].sd)V:'&*m:j&}(O`\y6/8@}oo4VG!bVrqLOeGUR^MExfw-Awc-L]zz?JqQuS&;`C#<7sb[+,NjEUP=TPp$ST3!#DfzxIu;^wJ4+c{`2^9d*nv(O#C)S48X+`&#7E5\Cw+n;Ja4...

output:


result:


Test #10:

score: 0
Time Limit Exceeded

input:

16900 16900 130
6)w8p]`Q%T|Ijb+dD@y]xuQf*3z?lKU32J1}rrjdWmG==sShI_Z!s=hIo&3S'9_5LYqp|HK(\GY9J@gH'C=Rh;AHh#T"L{1kY(+->Q<;gJz3NZ*9>yHV\6QGO@o~(kR|nuFShs[H+5PK_Q2KVI_bqWDAetYG|5es)idNhysSseL~%3@PV=vA(Q'e`%iCE~iJ{VTU8jHQ!+Yj+V=Z%Bp&Y*-NV8r&5*y7#CsFl]2]8zAR+I;JN%a[4_Go?-I{.{`_%)6_q2FqDv+`Md1$l4DI$+-l`)^j...

output:


result: