QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#649965 | #7705. Make Your Own Morse Code Palindrome | enze114514 | TL | 107ms | 3836kb | C++20 | 2.7kb | 2024-10-18 11:54:28 | 2024-10-18 11:54:29 |
Judging History
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