QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#275229 | #7882. Linguistics Puzzle | zzzYheng | TL | 231ms | 3740kb | C++14 | 2.5kb | 2023-12-04 15:22:27 | 2023-12-04 15:22:28 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using namespace std;
const int kMaxN = 55;
int T;
int n;
vector<string> P, Q, QQ;
pair<int, int> cntP[kMaxN];
pair<int, int> cntQ[kMaxN];
vector<int> vec[kMaxN];
int p[kMaxN];
bool vis[kMaxN];
string ans;
void dfs(int now) {
if (now == n) {
QQ.clear();
for (int i = 0; i < n * n; ++i) {
string s;
for (int j = 0; j < P[i].size(); ++j) {
s += p[P[i][j]];
}
QQ.emplace_back(s);
}
sort(QQ.begin(), QQ.end());
//for (string it : QQ) cout << it << ' ';
//cout << '\n';
if (QQ == Q) {
ans = "";
for (int i = 0; i < n; ++i) {
if (p[i] < 26) ans += 'a' + p[i];
else ans += 'A' + p[i] - 26;
}
return;
}
return;
}
for (auto it : vec[now]) {
if (!vis[it]) {
vis[it] = 1;
p[now] = it;
dfs(now + 1);
if (ans != "flag") return;
vis[it] = 0;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> T;
while (T--) {
cin >> n;
P.clear(), Q.clear();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
int x = i * j;
string s;
if (x < n) {
s += x;
}
else {
s += x / n;
s += x % n;
}
P.emplace_back(s);
}
}
for (int i = 0; i < n * n; ++i) {
string s;
cin >> s;
for (int i = 0; i < s.size(); ++i) {
if ('a' <= s[i] && s[i] <= 'z') s[i] = s[i] - 'a';
else s[i] = s[i] - 'A' + 26;
}
Q.emplace_back(s);
}
sort(P.begin(), P.end());
sort(Q.begin(), Q.end());
//for (int i = 0; i < n * n; ++i) cout << P[i] << ' ';
//cout << '\n';
//for (int i = 0; i < n * n; ++i) cout << Q[i] << ' ';
//cout << '\n';
fill(cntP, cntP + n, make_pair(0, 0));
fill(cntQ, cntQ + n, make_pair(0, 0));
for (string it : P) {
++cntP[it[0]].first;
if (it.size() > 1) ++cntP[it[1]].first;
}
//cout << "( " << i << ' ' << cntP[i].first << ' ' << cntP[i].second << '\n';
for (string it : Q) {
++cntQ[it[0]].first;
if (it.size() > 1) ++cntQ[it[1]].first;
}
//cout << ") " << i << ' ' << cntQ[i].first << ' ' << cntQ[i].second << '\n';
for (int i = 0; i < n; ++i) vec[i].clear();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (cntP[i] == cntQ[j]) {
//cout << "* " << i << ' ' << j << '\n';
vec[i].emplace_back(j);
}
}
}
ans = "flag";
fill(vis, vis + n, 0);
dfs(0);
cout << ans << '\n';
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3528kb
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: 1ms
memory: 3492kb
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: 212ms
memory: 3660kb
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: 25ms
memory: 3720kb
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: 123ms
memory: 3652kb
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: 230ms
memory: 3664kb
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: 15ms
memory: 3740kb
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: 186ms
memory: 3660kb
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: 55ms
memory: 3620kb
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: 154ms
memory: 3676kb
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: 231ms
memory: 3640kb
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: 17ms
memory: 3640kb
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: 3564kb
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: -100
Time Limit Exceeded
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 ...