QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#688222 | #7705. Make Your Own Morse Code Palindrome | dbaumg | AC ✓ | 0ms | 3848kb | C++20 | 2.6kb | 2024-10-30 00:57:35 | 2024-10-30 00:57:35 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
map<char, string> m;
pair<ll, string> solve(string s) {
ll n = s.size();
ll dp[n + 1] = {};
char prev[n + 1] = {};
fill_n(dp, n + 1, 1e9);
dp[0] = 0;
for (int i = 0; i < n; i++) {
for (auto p : m) {
string cur = p.second;
reverse(cur.begin(), cur.end());
if (i + cur.size() - 1 >= n)
continue;
bool valid = true;
for (int j = 0; j < cur.size(); j++)
valid &= s[i + j] == cur[j];
if (valid && dp[i + cur.size()] > dp[i] + 1) {
dp[i + cur.size()] = dp[i] + 1;
prev[i + cur.size()] = p.first;
}
}
}
string ans = "";
ll cur = n;
while (cur > 0) {
ans += prev[cur];
cur -= m[prev[cur]].size();
}
return {dp[n], ans};
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
m['A'] = ".-";
m['B'] = "-...";
m['C'] = "-.-.";
m['D'] = "-..";
m['E'] = ".";
m['F'] = "..-.";
m['G'] = "--.";
m['H'] = "....";
m['I'] = "..";
m['J'] = ".---";
m['K'] = "-.-";
m['L'] = ".-..";
m['M'] = "--";
m['N'] = "-.";
m['O'] = "---";
m['P'] = ".--.";
m['Q'] = "--.-";
m['R'] = ".-.";
m['S'] = "...";
m['T'] = "-";
m['U'] = "..-";
m['V'] = "...-";
m['W'] = ".--";
m['X'] = "-..-";
m['Y'] = "-.--";
m['Z'] = "--..";
m['0'] = "-----";
m['1'] = ".----";
m['2'] = "..---";
m['3'] = "...--";
m['4'] = "....-";
m['5'] = ".....";
m['6'] = "-....";
m['7'] = "--...";
m['8'] = "---..";
m['9'] = "----.";
string s;
getline(cin, s);
string t = "";
for (char c : s)
t += m[c];
ll k = 0;
for (int i = 1; i <= t.size(); i++) {
string s1 = "";
for (int j = 0; j < i; j++)
s1 += t[ll(t.size()) - j - 1];
string s2 = s1;
reverse(s2.begin(), s2.end());
if (s1 == s2)
k = i;
}
for (int i = 0; i < k; i++)
t.pop_back();
auto ans = solve(t);
if (k == 0) {
t.push_back('-');
auto p1 = solve(t);
t.pop_back();
t.push_back('.');
auto p2 = solve(t);
ll mn = min(p1.first, p2.first);
pair<ll, string> ans;
if (mn == p1.first) ans = p1;
if (mn == p2.first) ans = p2;
}
cout << ans.first << " " << ans.second;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3560kb
input:
FOOT
output:
1 L
result:
ok correct
Test #2:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
FOOTS
output:
3 0QI
result:
ok correct
Test #3:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
FOOTS
output:
3 0QI
result:
ok correct
Test #4:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
FOOTSTOOL
output:
0
result:
ok correct
Test #5:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
OOTNX
output:
2 J0
result:
ok correct
Test #6:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
3 FRENCH HENS
output:
6 5RCLXB
result:
ok correct
Test #7:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
TWAS THE NIGHT BEFORE XMAS
output:
13 YXFOL46PF4VPT
result:
ok correct
Test #8:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
1A2B3C4D5E6F7G8H9I10J
output:
18 0695OPUC5646R848YG
result:
ok correct
Test #9:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
A PARTRIDGE IN A PEAR TREE
output:
8 QF3FFCXC
result:
ok correct
Test #10:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
TEN LORDS ALEAPING
output:
9 BQ4L4R8XA
result:
ok correct
Test #11:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
XABCDQRST1234567890123456789
output:
7 6CZCBQU
result:
ok correct
Test #12:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
ASDFGHJKLQWERTYUIOPMNBVCXZ987
output:
23 ZO12FY5ROP8XYLQPRY73LFF
result:
ok correct
Test #13:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
THE QUICK BROWN FOX JUMPS OVER
output:
17 24YXQ2C2JLUCCLY5T
result:
ok correct
Test #14:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
1234567891 IS A PRIME NUMBER 0
output:
18 L37YVUC59123456789
result:
ok correct
Test #15:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
INTRANSIGENCE
output:
0
result:
ok correct
Test #16:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
ANTICKING ANTICKING WRECKING A
output:
5 CRCXP
result:
ok correct
Test #17:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
output:
1 E
result:
ok correct
Test #18:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
ISO9001 "IEEEEEEEEEEEEEEEEEEEE
output:
6 90018S
result:
ok correct