QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#279116#7882. Linguistics PuzzleSGColinWA 4ms3900kbC++202.2kb2023-12-08 11:16:552023-12-08 11:16:55

Judging History

你现在查看的是最新测评结果

  • [2023-12-08 11:16:55]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:3900kb
  • [2023-12-08 11:16:55]
  • 提交

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