QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#755961#7882. Linguistics Puzzletkt0506WA 7ms3596kbC++141.7kb2024-11-16 18:31:192024-11-16 18:31:19

Judging History

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

  • [2024-11-16 18:31:19]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:3596kb
  • [2024-11-16 18:31:19]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int N = 60;

int c1[N], c2[N][N], cnt[N*N], ans[N];
bool vis[N];

int f(char a){
    if('a' <= a)return a-'a';
    else return a-'A'+26;
}

bool f2 = 0;

void precompute(int n){
    memset(cnt, 0, sizeof cnt);
    memset(c1, 0, sizeof c1);
    memset(c2, 0, sizeof c2);
    memset(vis, 0, sizeof vis);
    memset(ans, -1, sizeof ans);
    for(int i=0; i<n; i++)for(int j=0; j<n; j++)cnt[i*j]++;
    f2 = 0;
}

void dfs(int u, int n){ 
    if(u >= n){
        f2 = 1;
        return ;
    }
    for(int i=0; i<n; i++){ // match char u -> int i 
        if(vis[i])continue; // int used
        vis[i] = 1;
        if(cnt[i] == c1[u]){
            bool f = 1;
            for(int j=0; j<u; j++){
                // char j : int ans[j]
                // char u : int i 
                if(ans[j] && c2[j][u] != cnt[ans[j]*n+i])f = 0;
                if(i && c2[u][j] != cnt[i*n+ans[j]])f = 0;
            }
            if(f){
                // cout << "char: " << u << " <-> int: " << i << "\n"; 
                ans[u] = i;
                dfs(u+1,n);
                if(f2)break;
            }
        }
        vis[i] = 0;
    }
}

void solve(){
    int n;
    cin >> n;

    precompute(n);
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            string s;
            cin >> s;
            if(s.length() == 1) c1[f(s[0])]++;
            else c2[f(s[0])][f(s[1])]++;
        }
    }

    dfs(0, n);
    char a2[n+1];
    for(int i=0; i<n; i++)a2[ans[i]] = (char)(i+'a');
    a2[n] = 0;
    cout << a2 << "\n";
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--)solve();
}

詳細信息

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: 3528kb

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: 7ms
memory: 3596kb

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:

wrong answer invalid character { at case #25