QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#649965#7705. Make Your Own Morse Code Palindromeenze114514TL 107ms3836kbC++202.7kb2024-10-18 11:54:282024-10-18 11:54:29

Judging History

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

  • [2024-10-18 11:54:29]
  • 评测
  • 测评结果:TL
  • 用时:107ms
  • 内存:3836kb
  • [2024-10-18 11:54:28]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

#define pb push_back

const ld pi = 3.14159265358979323846;
const ll INF = 1e18;

template<typename T>
T chmax(T a, T b) {
    return a > b ? a : b;
}

template<typename T>
T chmin(T a, T b) {
    return a > b ? b : a;
}

const int N = (int)1e5 + 1, M = N * 2;

unordered_map<char, string> mp = {
    {'A', ".-"},   
    {'B', "-..."}, 
    {'C', "-.-."}, 
    {'D', "-.."},  
    {'E', "."},    
    {'F', "..-."},
    {'G', "--."},  
    {'H', "...."}, 
    {'I', ".."},   
    {'J', ".---"}, 
    {'K', "-.-"},  
    {'L', ".-.."},
    {'M', "--"},   
    {'N', "-."},   
    {'O', "---"},  
    {'P', ".--."}, 
    {'Q', "--.-"}, 
    {'R', ".-."},
    {'S', "..."},  
    {'T', "-"},    
    {'U', "..-"},  
    {'V', "...-"}, 
    {'W', ".--"},  
    {'X', "-..-"},
    {'Y', "-.--"}, 
    {'Z', "--.."},
    {'0', "-----"}, 
    {'1', ".----"}, 
    {'2', "..---"}, 
    {'3', "...--"}, 
    {'4', "....-"},
    {'5', "....."}, 
    {'6', "-...."}, 
    {'7', "--..."}, 
    {'8', "---.."}, 
    {'9', "----."}
};

vector<char> ch;

int pld(string t){
    int uwu = 0;
    for(int l = 0, r = t.size() - 1; l < r; l++, r--){
        if(t[l] != t[r]){
            uwu = 1;
        }
    }
    return !uwu;
}

void dfs(string s, int id, vector<char> v){
    if(v.size() >= ch.size()){
        return;
    }
    if(id == s.size()){
        ch.clear();
        for(auto c : v){
            ch.pb(c);
        }
        return;
    }

    for(auto [key, val] : mp){
        int len = val.size();
        if(id + len > s.size() || s.substr(id, len) != val) continue;
        v.pb(key);
        dfs(s, id + len, v);
        v.pop_back();
    }
}

void solve(){
    string input, s;
    getline(cin, input);

    for(char c : input){
        if(isalnum(c)){
            s += c;
        }
    }

    string ds = "";

    for(auto &c : s){
        c = toupper(c);
        ds += mp[c];
        ch.pb(c);
    }

    if(pld(ds)){
        cout << 0 << endl;
        return;
    }

    for(int i = ds.size() - 1; i >= 0; i--){
        string t = ds.substr(i);
        if(pld(t)){
            string qwq = ds.substr(0, i);
            reverse(qwq.begin(), qwq.end());
            vector<char> v;            
            dfs(qwq, 0, v);
        }
    }

    cout << ch.size() << " ";
    for(auto v : ch){
        cout << v;
    } cout << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    // cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3576kb

input:

FOOT

output:

1 L

result:

ok correct

Test #2:

score: 0
Accepted
time: 1ms
memory: 3640kb

input:

FOOTS

output:

3 29D

result:

ok correct

Test #3:

score: 0
Accepted
time: 1ms
memory: 3572kb

input:

FOOTS

output:

3 29D

result:

ok correct

Test #4:

score: 0
Accepted
time: 1ms
memory: 3572kb

input:

FOOTSTOOL

output:

0

result:

ok correct

Test #5:

score: 0
Accepted
time: 0ms
memory: 3836kb

input:

OOTNX

output:

2 J0

result:

ok correct

Test #6:

score: 0
Accepted
time: 107ms
memory: 3580kb

input:

3 FRENCH HENS

output:

6 5RKFL7

result:

ok correct

Test #7:

score: -100
Time Limit Exceeded

input:

TWAS THE NIGHT BEFORE XMAS

output:


result: