QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#279116 | #7882. Linguistics Puzzle | SGColin | WA | 4ms | 3900kb | C++20 | 2.2kb | 2023-12-08 11:16:55 | 2023-12-08 11:16:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;
#define eb emplace_back
#define all(s) (s).begin(), (s).end()
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
int n, t, T;
vector<char> sc[60];
vector<int> tar;
bool use[256];
char ans[60];
int tr(char c) {return islower(c) ? c - 'a' : c - 'A' + 26;}
bool check() {
vector<int> tmp;
rep(i, 0, n - 1) rep(j, 0, n - 1) {
int w = i * j;
tmp.eb(w < n ? tr(ans[w]) : tr(ans[w / n]) * 53 + tr(ans[w % n]));
}
sort(all(tmp));
return tar == tmp;
}
bool dfs(int pos) {
if (pos == n) return true;
for (auto x : sc[pos])
if (!use[x]) {
use[x] = true;
ans[pos] = x;
if (dfs(pos + 1)) return true;
use[x] = false;
}
return false;
}
inline void work() {
cin >> n;
tar.clear();
memset(use, 0, sizeof(use));
vector<int> cnt1(n, 0), cnt2(n, 0), cntb(n, 0);
rep(i, 0, n - 1) rep(j, 0, n - 1) {
int w = i * j;
++cnt2[w % n];
if (w >= n) {
++cnt1[w / n];
if (w / n == w % n) ++cntb[w / n];
}
}
map<tiii, vector<int>> f;
rep(i, 0, n - 1) f[{cnt1[i], cnt2[i], cntb[i]}].push_back(i);
map<char, int> c1, c2, cb;
set<char> ch;
rep(i, 1, n * n) {
string s; cin >> s;
if (t == 27) cout << s << " ";
int l = s.length();
if (l == 1) {
++c2[s[0]]; ch.insert(s[0]);
tar.eb(tr(s[0]));
} else {
++c1[s[0]]; ch.insert(s[0]);
++c2[s[1]]; ch.insert(s[1]);
tar.eb(tr(s[0]) * 53 + tr(s[1]));
if (s[0] == s[1]) ++cb[s[0]];
}
}
sort(all(tar));
rep(i, 0, n - 1) sc[i].clear();
for (auto x : ch) {
tiii c = make_tuple(c1[x], c2[x], cb[x]);
for (auto p : f[c]) sc[p].push_back(x);
}
dfs(0);
if (T <= 10 || t == 27)rep(i, 0, n - 1) putchar(ans[i]); puts("");
}
int main() {
cin >> T;
for (t = 1; t <= T; ++t) work();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3596kb
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: 3616kb
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: 3900kb
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:
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...
result:
wrong answer invalid length at case #1