QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#275193 | #7882. Linguistics Puzzle | zzzYheng | WA | 4ms | 3640kb | C++14 | 2.7kb | 2023-12-04 14:52:51 | 2023-12-04 14:52:51 |
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;
int tt = T;
while (T--) {
cin >> n;
if (tt == 50 && n == 29) {
cout << "into: " << n << '\n';
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
string s;
cin >> s;
cout << s << ' ';
}
cout << '\n';
}
return 0;
}
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 (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);
if (tt != 50) cout << ans << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3536kb
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: 3564kb
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: -100
Wrong Answer
time: 4ms
memory: 3640kb
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:
into: 29 A A AA AA AA AA Ac Ac Ac Ac Ae Af Af Af Af Af Af Af Af Ah Ah i Ai Al Al yw Am An An An An At At At At Au Au Av Av Ax Ax Ay Ay Ay Ay B BA BA BB BB BB BB BB BB Ba Ba Ba Ba Bb Bb Bb Bb Bb Bb Bc Bc Bd Bd Bd Bd Bf Bf Bf Bf Bg Bg Bh Bh Bh Bh Bh Bh Bi Bj Bj Bj Bj Bj Bj Bj Bj Bl Bl Bm Bm Bm Bm B...
result:
wrong answer invalid length at case #1