QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#302999 | #15. 虫逢 | Unknown1508 | 10 | 5ms | 3908kb | C++20 | 3.5kb | 2024-01-11 16:42:45 | 2024-01-11 16:42:46 |
Judging History
answer
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
void main_program();
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
main_program();
}
using u8 = uint8_t;
template <class T>
using uset = unordered_set<T>;
int n, M, L;
string s;
vector<int> mapping, answer;
vector<vector<int>> A;
int newval = 0;
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++;
}
int remaining = 0;
map<pair<int, int>, bool> cache;
bool equivalent(int a, int b){
if (a > b) swap(a, b);
if (cache.count({a, b})) return cache[{a, b}];
int cnt = 0;
int it1 = 0, it2 = 0;
while (it1 < L && it2 < L){
if (A[a][it1] == A[b][it2]){
it1++; it2++; cnt++;
}
else if (A[a][it1] < A[b][it2]) it1++;
else it2++;
if (remaining >= max(100, n/10) && it1 + it2 >= 5 && cnt == 0) return false;
}
return cache[{a, b}] = (cnt >= L/2);
}
using u32 = uint32_t;
u32 faster_rand(){
static u32 state = 2945725598;
state += 9877345679;
u32 z = state;
z = (z ^ (z >> 14)) * 897698346;
z = (z ^ (z >> 12)) * 797536943;
return z ^ (z >> 15);
}
vector<int> vec;
void run_hash_function(){
for (auto &val: vec) val = faster_rand();
}
void main_program(){
cin >> n >> M >> L;
cin >> s;
create_mapping();
answer.assign(n * 2, -1);
A.assign(n * 2, vector<int>(L));
map<int, vector<int>> mp;
map<int, int> compress;
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);
A[i][j] = H;
compress[H] = 1;
}
}
for (auto &[key, value]: compress) value = newval++;
for (int i = 0; i < n * 2; i++){
for (int j = 0; j < L; j++){
A[i][j] = compress[A[i][j]];
}
}
for (int i = 0; i < n * 2; i++){
sort(A[i].begin(), A[i].end());
}
// for (int i = 0; i < n * 2; i++){
// for (int j = 0; j < L; j++){
// cout << A[i][j] << " ";
// }
// cout << "\n";
// }
vec.resize(newval);
remaining = n;
vector<pair<int, int>> group(n * 2);
while (remaining){
// cout << "New iteration" << endl;
vector<int> order;
run_hash_function();
for (int i = 0; i < n * 2; i++){
if (answer[i] >= 0) continue;
group[i] = {INT_MAX, INT_MAX};
order.push_back(i);
for (int j = 0; j < L; j++){
group[i].first = min(group[i].first, vec[A[i][j]]);
}
}
int crridx = 0;
run_hash_function();
for (int i = 0; i < n * 2; i++){
for (int j = 0; j < L; j++){
group[crridx].second = min(group[crridx].second, vec[A[i][j]]);
}
crridx++;
}
sort(order.begin(), order.end(), [&](int idx1, int idx2){
return group[idx1] < group[idx2];
});
// for (auto idx: order) cout << "idx = " << idx << endl;
int sz = order.size();
for (int i = 0; i < sz; i++){
int ii = order[i];
if (answer[ii] >= 0) continue;
for (int j = i + 1; j < sz; j++){
int jj = order[j];
if (group[jj] != group[ii]) break;
if (equivalent(ii, jj)){
answer[ii] = jj;
answer[jj] = ii;
remaining--;
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: 5ms
memory: 3908kb
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: 0
Time Limit Exceeded
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:
result:
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+`E5\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...