QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#591339 | #7882. Linguistics Puzzle | limpid | AC ✓ | 7ms | 3900kb | C++14 | 3.3kb | 2024-09-26 15:28:50 | 2024-09-26 15:28:51 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cassert>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
inline int read(){
int f=1,ans=0; char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
return f*ans;
}
const int MAXN = 65;
int cas, A[MAXN][MAXN];
int Q(char c){
if(c >= 'a' && c <= 'z') return c - 'a';
return 26 + c - 'A';
}
char Q_(int x){
if(x <= 25) return 'a' + x;
return (x - 26) + 'A';
}
int buc[MAXN][MAXN]; bool vis[MAXN]; int Ans[MAXN], N, GGG[MAXN];
vector<int> vec[MAXN], g, vec1[MAXN];
char str[5];
char Ans_i[MAXN];
void Print(vector<int> t){
for(auto w: t) printf("%d ", w); printf("\n");
return;
}
int buc1[MAXN * MAXN];
bool check(){
memset(buc1, 0, sizeof(buc1));
for(int i = 0; i < N; i++) buc1[Ans[i]] += GGG[i];
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
if(buc[i][j]){
if(Ans[i] == 0) assert(0);
buc1[Ans[i] * N + Ans[j]] += buc[i][j];
}
}
}
for(int i = 0; i < N; i++) for(int j = 0; j < N; j++){
if(buc1[i * j] == 0) return 0;
buc1[i * j]--;
}return 1;
}
int main(){
//freopen("1.in", "r", stdin);
cas = read();
while(cas--){
N = read(); for(int i = 0; i < N; i++) vec[i].clear(), vec1[i].clear();
memset(A, 0, sizeof(A)); memset(buc, 0, sizeof(buc)); memset(GGG, 0, sizeof(GGG));
memset(vis, 0, sizeof(vis));
memset(Ans, -1, sizeof(Ans));
for(int i = 1; i <= N * N; i++){
scanf("%s", str + 1); int len = strlen(str + 1);
if(len == 1) GGG[Q(str[1])]++;
else buc[Q(str[1])][Q(str[2])]++;
}
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
int w = i * j;
A[w / N][w % N]++;
}
}
vec[0].pb(2 * N - 1);
for(int i = 1; i < N; i++){
g.clear();
for(int j = 0; j < N; j++) if(A[i][j]) g.pb(A[i][j]);
sort(g.begin(), g.end());
vec[i] = g;
vec[i].pb(A[0][i]);
}
for(int i = 0; i < N; i++){
g.clear();
for(int j = 0; j < N; j++) if(buc[i][j]){
g.pb(buc[i][j]);
}
sort(g.begin(), g.end());
vec1[i] = g; vec1[i].pb(GGG[i]);
}
for(int i = 0; i < N; i++){
if(GGG[i] == 2 * N - 1){
Ans[i] = 0; vis[0] = 1; continue;
}
for(int j = 1; j < N; j++){
if(vis[j]) continue;
if(vec1[i].size() != vec[j].size()) continue;
bool flag = 1;
for(int k = 0; k < vec1[i].size(); k++) flag &= (vec1[i][k] == vec[j][k]);
if(flag){
Ans[i] = j; vis[j] = 1; break;
}
}
}
int px = -1, py = -1;
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
if(i == j) continue;
if(vec[i].size() != vec[j].size()) continue; bool flag = 1;
for(int t = 0; t < vec[i].size(); t++) flag &= (vec[i][t] == vec[j][t]);
if(flag){
px = i, py = j;
break;
}
}
}
int posx = -1, posy = -1;
if(px != -1){
for(int i = 0; i < N; i++) if(Ans[i] == px){posx = i; break;}
for(int i = 0; i < N; i++) if(Ans[i] == py){posy = i; break;}
}
if(!check()){
swap(Ans[posx], Ans[posy]);
}
for(int i = 0; i < N; i++) Ans_i[Ans[i]] = Q_(i);
for(int i = 0; i < N; i++) cout << Ans_i[i]; cout << endl;
}
}/*
2
3
a b a b b b b c cc
4
d d d d d c b a d b cd cb d a cb bc
*/
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3880kb
input:
2 3 a b a b b b b c cc 4 d d d d d c b a d b cd cb d a cb bc
output:
bca dcba
result:
ok OK
Test #2:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
2 4 d a a bc ba bc b a a a d a a cb c c 4 a b da b b d ad b db b a c da b c b
output:
abcd bdac
result:
ok OK
Test #3:
score: 0
Accepted
time: 3ms
memory: 3816kb
input:
50 3 b b b a a c b b cc 4 d ab c ad d b ba ab c b d d d d d a 5 a aa aa ab ab ae b b e c c c ba c c c c dd d d dd c e c e 6 a ca a a a a a a ce a a b ba ba bc bc bd be e c c ca a cd cd be d d dc dc e e a eb f f 7 a a a a a a a a cf a a a a b b b b c c c cf a dd d dc d dd e f ed ee ee fb eg eg eg eg ...
output:
bca dabc cadbe abcdef aefdcgb fcheabgd bhgfedcia jhcgfideba fjbadkegcih klhgjbaedcif igkjmclfedhba nflijahgmbdcek anmlfijbgkhdceo nofmlkjchdbegipa aponblgjihcfqdkme iqmonhckfrpgjedlba prisodmbkjqghfencla tcrdpoaklmjihfgeqsbn utiraponmlksghjfecdbq qotsrvjunmlkpiegfhdcba pvutsrhwoimlkjnqgfedbca xbvuts...
result:
ok OK
Test #4:
score: 0
Accepted
time: 3ms
memory: 3696kb
input:
50 3 a a b c c c c bb c 4 a c ab b c ba ba c c a bc c c c d d 5 a a a b b b b b b c b d c b cc cc b d de e ea ed ed ee ee 6 a a ac ac b b b be ef c ca cb ea f cf d d e ca eb eb ec f ef c f f f f f f f f f cf ec 7 ag a a a ag b bb bb bd bd bf bf bf e bg c c c c c c c c c c c e c ga d da dd dd bf e e ...
output:
cba cbad becda fecabd cbgdafe abgfechd abhgeicdf ahfdgcebij bagedfcihjk abcdhkgifjle fkgdeachblijm alcdbfgjihkmen jfobedghiaklmcn ahgdemcnijklfbop aecdjlbhiqkfmnopg aecdbfjhkimlgnopqr afcdqbghriklmnopejs dbcaefghijktmnosqrpl qbisefgpcjklmnohdratu pdcbeaghijmlknofqrstuv aoedqfghijkclnbpmrstuvw atcdef...
result:
ok OK
Test #5:
score: 0
Accepted
time: 3ms
memory: 3740kb
input:
50 3 a c a a bb b c a a 4 dc c a b b c ad c c c c c d da da a 5 a d a a a e a a ce a b bb bb c cc cc cd cd a d a e b e dc 6 d ab a ab b b ba ba bd bd bf c c d d a d d d eb d d d d e ea eb d ed ed ef ef f f f fe 7 a a a a ea f bb bb bg g cb cb cc cc f cd cd cd ce d d dc e e b ea ec ec ee eg eg f f f ...
output:
abc cdab acbde debafc fcebgda gafedbhc ihbfedagc haiebjcfdg chkefdigbaj echkagbilfjd ajcmhgbidklfe ibmckfgaehndjl ogfhbicekndljma ngmdkpiblcfeajho qlgbcipjkdehnfmao qadoilgcepfbnjkhrm kdiceagnlrjhbosfqmp iakrbqdgmescjpnlhotf nhedbluojtakqpgscrimf esflhqkbnoamrduivgcptj wmjqcgauvlhofdnpbsrteki unsbtm...
result:
ok OK
Test #6:
score: 0
Accepted
time: 3ms
memory: 3760kb
input:
50 3 b a a c c c bb c c 4 a cb b d bc c cd a cb d d b d d d d 5 a a a b b dd c c cc d cc e db e da bd e db e e e e dd e e 6 a a b b f ed c c b cd d d db f dc df df e eb eb f be ed ef ef f f cd f ec f f f dc f f 7 fb a a a b b bf c c c ce ce d d g dd dd e e g ea ec ef ee ef ec f fb g fb fb fd fd fe f...
output:
cba dcba edcba fedcba gfedcba hgfedcba ihgfedcba jihgfedcba kjihgfedcba lkjihgfedcba mlkjihgfedcba nmlkjihgfedcba onmlkjihgfedcba ponmlkjihgfedcba qponmlkjihgfedcba rqponmlkjihgfedcba srqponmlkjihgfedcba tsrqponmlkjihgfedcba utsrqponmlkjihgfedcba vutsrqponmlkjihgfedcba wvutsrqponmlkjihgfedcba xwvuts...
result:
ok OK
Test #7:
score: 0
Accepted
time: 3ms
memory: 3884kb
input:
50 3 a bb b a a c a c a 4 a b a a a a a a ba bc c cb c bc d d 5 a a a a bd a a a a b bb e a bd be c c cc db d e cc e bb d 6 a a a a a a e a ba d e b ba a bc bc bd be be c c ca ca cd cd ce d a dc dc e a a eb f f 7 a cg a a cb a a a a a c a a b bb bb bc bd bd bf bf bf bf a c cb a cc ce ce cg a d e ec ...
output:
abc abcd abcde abcdef abcdefg abcdefgh abcdefghi abcdefghij abcdefghijk abcdefghijkl abcdefghijklm abcdefghijklmn abcdefghijklmno abcdefghijklmnop abcdefghijklmnopq abcdefghijklmnopqr abcdefghijklmnopqrs abcdefghijklmnopqrst abcdefghijklmnopqrstu abcdefghijklmnopqrstuv abcdefghijklmnopqrstuvw abcdef...
result:
ok OK
Test #8:
score: 0
Accepted
time: 3ms
memory: 3780kb
input:
50 3 a c a a b bb a a c 4 b c b ab b b ad a c b d d b b da ad 5 c c c c dd c bb ed b e c c da a d a c e b de a bb dd c de 6 d a a c bf da a a a dc e a a a fd da c f fa a fc d fb b db e cd cd b a b fa a fd dc fb 7 fd f e g ff e g e e fc e bf e fb fd c e c g bg d ff e g a e bf df ba ab ab fd bg e ba f...
output:
abc badc cdbea afdcbe efbcadg agdbhfec bdifahcge jfbgdeachi ajhbgfeickd fkjehgbidcal clijmhgfbdeka nibkjghafcdelm bnlokjihgaedcmf pfcmlboihkjednga eponjlbgihdfqmcka rijqnmlkgohpfecdba sdgponmlkqihjefrcba tsgiponflqakhrmedcbj ltsiqpobmunjghrfedcka vdtfrqponmsjkibgleucha avutsrnpoqmldjihgfwkcbe xwvstu...
result:
ok OK
Test #9:
score: 0
Accepted
time: 3ms
memory: 3696kb
input:
50 3 a c c c b bb c c a 4 dc a cd d da c a a b a a a a dc c b 5 be b d cc a a d bb e a be d d cc eb e c ba d d d d d bb c 6 e ad ef db b c ad db b d da c b fe f fe a b fb b b da fb b a b e fd fd d b b de b fa e 7 dd f bb de a bd c aa bb c e c f f f f ba f f aa ae f dc f db dc bg f ba g bg c g gb ed ...
output:
cba adcb dbcea bfdaec fbdaegc eabdfcgh abhfcegdi jfcdbaehig abcedfhigjk khcfadgibjel jdclefghibkam lgcdejbhifknma abcdehfligkjnmo ikognfdhajblmecp amoiefghdjblkpcnq kbcdehgqioalmnjpfr ancfesrhijklmgopqbd amgdfcheijklbnopqrst fbcdeoghrjkainlpqmstu dbcoefhaijklmgnpqrstuv nbcdefghiwkljaosqmptuvr abcsuf...
result:
ok OK
Test #10:
score: 0
Accepted
time: 3ms
memory: 3780kb
input:
50 3 b cc a b b b a c b 4 ab c ba d a c c ba a d c c c c b bc 5 cc d bd c a a a be e b a a e a a a bb a db cc bd e d bb c 6 ed af af d be a ea fa fd c a b fa b e eb fb eb ef c d d b fd d f ef d f d d ed d d d d 7 c aa d ee g d g aa a ff f d be d d d e ac d d ea eb ea be d f af d eg g d b eb fb c ff ...
output:
bca cbad abcde defabc daefbcg dhebagfc bahifcdeg bceagfdihj gbhfkcdeiaj jialecgbfdkh idjcgfkaemhbl ngbecmjafkhdil bcoeaidjnkfglhm emnodgaihcfpjklb bqcgofjinlaekphdm kgceolrnhqipbafdjm eflgbscoqpndmkajhir bgmfthncdekqjrapiosl sdhtprilkobacqjnmgeuf bjqtdlfurspvcaehoingkm lderwoqsjpnhvfmcbuikgat noukih...
result:
ok OK
Test #11:
score: 0
Accepted
time: 3ms
memory: 3872kb
input:
50 3 c c c bb a a c c b 4 b d cb cb b a bc d d cd d c a d d d 5 c b e e bd da e d cc dd a e e db e db b e a a dd c e e cc 6 eb df f f eb d be f f c d a f df cd c dc b ef dc f f e ec f ef b cd ed db f f ed a b f 7 g fb ea b ec fe g f c bf c g dc dd b e g fb d ec ef ee ce ff c a fd g ef dd e g d g fb ...
output:
cba dcba edcba fedcba gfedcba hgfedcba ihgfedcba jihgfedcba kjihgfedcba lkjihgfedcba mlkjihgfedcba nmlkjihgfedcba onmlkjihgfedcba ponmlkjihgfedcba qponmlkjihgfedcba rqponmlkjihgfedcba srqponmlkjihgfedcba tsrqponmlkjihgfedcba utsrqponmlkjihgfedcba vutsrqponmlkjihgfedcba wvutsrqponmlkjihgfedcba xwvuts...
result:
ok OK
Test #12:
score: 0
Accepted
time: 3ms
memory: 3808kb
input:
50 3 a a c c a b a a bb 4 b a c a a ba c a a a cb d d bc bc a 5 a db c e d e a d a a bd bb a e a b c bd be cc a bb a cc a 6 d ca a c d a c bc e f be ca ba a a ba b a eb cd bd a ce dc bc dc cd f a e a a a e be a 7 cb fb g ec cg a bf bd e d a cb a g a e dd f a c a cg bf bd bf g bf c d f a a e bc a ce ...
output:
abc abcd abcde abcdef abcdefg abcdefgh abcdefghi abcdefghij abcdefghijk abcdefghijkl abcdefghijklm abcdefghijklmn abcdefghijklmno abcdefghijklmnop abcdefghijklmnopq abcdefghijklmnopqr abcdefghijklmnopqrs abcdefghijklmnopqrst abcdefghijklmnopqrstu abcdefghijklmnopqrstuv abcdefghijklmnopqrstuvw abcdef...
result:
ok OK
Test #13:
score: 0
Accepted
time: 1ms
memory: 3676kb
input:
50 2 a b a a 2 a a a b 2 a a a b 2 b b b a 2 b a a a 2 b b b a 2 a b a a 2 a b a a 2 a a a b 2 a b b b 2 b b b a 2 b a a a 2 a b a a 2 a a b a 2 b a b b 2 a a b a 2 a a a b 2 b b a b 2 b b b a 2 a a b a 2 a b a a 2 a a a b 2 b b b a 2 a a a b 2 a b a a 2 a a a b 2 b a b b 2 a b b b 2 a a a b 2 a a a...
output:
ab ab ab ba ab ba ab ab ab ba ba ab ab ab ba ab ab ba ba ab ab ab ba ab ab ab ba ba ab ab ba ab ab ba ba ba ab ba ba ba ab ab ab ab ab ab ab ba ba ba
result:
ok OK
Test #14:
score: 0
Accepted
time: 7ms
memory: 3900kb
input:
50 52 uj Tp xo WR CE Ht q Wt RM sS mq Io ln TK eZ jH o mC hV ha hi a JH in hQ j Fg ar Wf Fp JH KR k xo gE qn az V Rs Pw nu un qv hH jH Da YK es XI b ec FN yg Z Tr Bw Ob gt pD k eo Xv lc no ln hz RW RF BZ rF yu k CI zu qJ Yz ex aI eU bn HW ej eo jP I jp xr ue yR V Tu zo Mv eh gz Xz mv FI hz mV ah Dh ...
output:
kehTRmxJHXqyrljaWYOSwigsnUzDuZbPtdCBIMcFpLNfvEGKoAVQ RjxrlcZngyWomHJtIOBYTUPViCvuGpXkQSdALDwzbfNaqFMhEseK FUcwvoLARpnGBQCDWdagNjyuthlYXefPJirZMSsbqHmIkTxzKOEV OujFdfKkElwsJLVmMYSZpXIeHDRyhACBvzroGcbtnagPNxUTWiQq wYtmrEDWGqIyVLNiHxzeTcgFkdQpBXnPZjKvARsJOoUbaSulfMhC SwZAyhRNJgMFOnWoDpbLTEXlBackuqjetIs...
result:
ok OK
Test #15:
score: 0
Accepted
time: 7ms
memory: 3744kb
input:
50 52 A A A AF AF AF AF AJ AJ AK AK AK AK AN AN AU AU AX AX AZ AZ Ab Ab Ab Ab Ah Ah Ah Ah Ar Ar As As At At Av Av Aw Aw B B BC BC BE BE BF BF BI BI BK BK BK BK BL BL BL BL BM BM BM BM BM BM BN BN BP BP BR BR BR BR BT BT BV BV BV BV BZ Bb Bb Bc Bc Bf Bf Bh Bh Bh Bh Bh Bh Bh Bh Bh Bh Bn Bn Bn Bn Bn Bn...
output:
ZYXWVUTSRQPONBLzJIHGFEDwMAKyxCvutsrqponmleaihgfkdcbj ZsXWVUTGRQPONMwKLIHSFEDCBAzyxJvutmrqponYlkjihgfedcba ZYXWVUTSRQlONMLKJIHGFBuwEAzyxCvDtsrqponmPkhijgfedcba ZYXWVUTSRQmONwLKJIHGFEDxBAzyCMvrtsuqdonPlkjihgfepcba ZcXWVUTSRkPONJLKMIHGFEDCBAzylwautsrqponmxQjihgfedYbv ZYXgVUTSwQPONMLKJIHGFyDCBezExRkutsr...
result:
ok OK
Test #16:
score: 0
Accepted
time: 7ms
memory: 3848kb
input:
50 52 A A A A AC AC AI AI AO AO AP AP AQ AQ AR AR Ab Ab Ai Ai Aj Aj Am Am An An Ao Ao Ao Ao Aq Aq Ar Au Au Az Az B B B B BF BF BK BK BK BK BK BK BN BN BO BU BU Ba Ba Bc Bc Be Be Bg Bg Bj Bj Bj Bj Bo Bo Bp Bp Br Br Bw Bw C C C C C C CA CA CD CD CG CG CO CO CS CS CW CW CW CW CX CX Cb Cb Cg Cg Cj Cj Co...
output:
abcdefghiylPmnWpqrstuvwxjzABCDEFGHIJKLTNOkQRSMUVoXYZ abcdefghUjklmnopNrstSZwxyzuBCDEFGHIJKLMqOPQRATiVWXYv cbadefghijklmnorqpstuUwMyzABCDEFGHIJKLxNPOQRSTvVWXYZ abcdefghiSklmnopqrstuLwxTzABCDUFGHIJKyMNOPQRjvEVWXYZ abcdefghijklmntpqrsvuowxyFAWCDEJGHIzKLMNOPQRSTUVBXYZ absiefghdAklmnopqrctuvwxyzjBCDEFGYI...
result:
ok OK
Test #17:
score: 0
Accepted
time: 7ms
memory: 3888kb
input:
50 51 kt Dt kq nP Ec X Bh V FT LL qS bN Rx x Av mT mw ax wS h A bt vV GJ ni Hw vK bV d v mL bL ub gy mx h In AE TG cK Fj jj zk Xd yo mB LX FA br UI Fa Li bH Ad Q Jt K Cq A pH Gz NX ak Gh bT be Rf U Ga vK Ha Kh Fu TT vd yT KY GG S qe P KD CF FF jz Bf nK Rh vA ca jA Kj Hp tw w Al o RW Wf KU fm Mr Jt m...
output:
hGbHvRAImjLFKnCByWDJgqEMTcOaUkdzwPVoelNtXsxrYfQpuSi FEfhbGwLQrljpSBzKoeTNJavguDycOCWtRPqidYxmAHVIkMUXsn IRpyjwiSTkJnaBAdOsUQFMcrfhLeHgNGltobxPWzuEXYKDqmVCv mMXWuYhVlSPoGHgNCBbdfcOrpyeRAtTaKvzxEILQnUisjwkFJDq afoTPBRjStKgMHyLIOklcdvNwuFDEnVsGApYzXhmiWCeQUxqJbr kFbiqnBwhMcPaHrNuQVeUJzgACmDfGxRXoyEsKSY...
result:
ok OK
Test #18:
score: 0
Accepted
time: 7ms
memory: 3844kb
input:
50 49 U ol fN hj aW n dQ qm OO ao T JQ an OO an QJ FF VV OT uE qE mK Cm Wj Op tA HH PR Rr ve Dn RV lP Op QO QW kV Od oL x Be IG Rz Ti o Mu VH OR pJ MU OL HS vB R qv Cu BF Vr BU l Ob z Qr ua Qt Qr nD dj aT RV vw ot JW dd dF cV OG RB nL qa aq Oq x F Qj bL RV lG nG Wj oM Vp Qx u Ho aS lL DU U U as JF O...
output:
UQavlfuROBodnpmIAVehiFqJGWCHLPMkgcKjDSbtTzENyxsrw KILacmoApesfEWShBMtiVCwNxryUJlFnbqQPzukdDvOTgGRjH ptndMgwRiVcPDoIThevubmCjlKOJHEBNsGzxaUQFqryWASfkL kvPWwzdeQyGUfTauoqiFINpEtxgcDAmBROKMJVnCjrlbSLhsH NWwrMBkDeCvtjLAVxTKOqmIEGuopyJRfsUHlgSzbhQPiaFcnd nSWLMvKCODqdblNAtfUrxkQGFHheBpERIwjcaoyJsuTmzgViP ...
result:
ok OK
Test #19:
score: 0
Accepted
time: 2ms
memory: 3872kb
input:
50 43 je cx EP yb Mp fI lI Ob DO Dt Ct N fn LD N EC MM Dy cK Ly xI KL KG eu je Q s JJ Lm xJ jx ss g hk Le qJ sE yn qh vD D DI fH p wH ak ej so GK ld N Mk so Ks Jd hd sL qQ DA DH ud CC ix jF br je fe jp Lo JB p yc fE ix N DQ Jl lJ wl N N bA lE Bc lD Ju wi H KM eE Dw eu N fO ux qg rL Fz pe AC Jn lk q ...
output:
NDeifKJwBsjrFLxqMylbCmuOzcpgnahEHoAQPGItkvd zpNbjomCFLuJEtgBfydscMieDHaqkPIvOlAwhKrxGnQ entcwrboxQildHBaJMEupvkNKOGjPImDAygshLCFzfq iMQCgvbzEhrNjHOpPacBuGfeLwJFAlxtkmonsqDKIdy IPfKnucrslDNGeFhwjqvCaibQmtoMxAJgBpkHOdyzEL LryNkBAGPpEvhxwbFIdMlaCsQzuienmHgofqDKtjOJc DgpBicMksnjAbCtyELdfHJPvmKalOGFNouhw...
result:
ok OK
Extra Test:
score: 0
Extra Test Passed