ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#206090 | #3168. 解码 | tanghexuan | 100 | 702ms | 50016kb | C++11 | 2.6kb | 2024-07-20 19:36:44 | 2024-07-20 20:26:14 |
answer
#include <bits/stdc++.h>
using namespace std;
static auto __fast_io = []()
{
ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
return 0;
}();
#define DEBUGx
#ifdef DEBUGx
#define TRC_PG(fmt, args...) fprintf(stderr, "\033[1;32m TRC_PG(%s:%d):\t\033[0m" fmt, __func__, __LINE__, ##args)
#define TRC_PR(fmt, args...) fprintf(stderr, "\033[1;31m TRC_PR(%s:%d):\t\033[0m" fmt, __func__, __LINE__, ##args)
#define debug fprintf(stderr, "Passing [%s] in LINE %d\t\n", __func__, __LINE__)
#endif
#ifndef DEBUGx
#define TRC_PG(...)
#define TRC_PR(...)
#define debug
#endif
const int MAX_N = 1e6 + 10;
const long long MOD1 = 888888829;
const long long BASE1 = 131;
long long hash1[2 * MAX_N];
long long hash2[2 * MAX_N];
long long base1[2 * MAX_N];
int n;
string s;
long long ans;
void input()
{
cin >> n >> s;
s = "#" + s;
}
long long getHash1(int l, int r)
{
if (l > r)
return 0;
return (hash1[r] - hash1[l - 1] * base1[r - l + 1] % MOD1 + MOD1) % MOD1;
}
long long getHash2(int l, int r)
{
if (l > r)
return 0;
return (hash2[l] - hash2[r + 1] * base1[r + 1 - l] % MOD1 + MOD1) % MOD1;
}
void init()
{
base1[0] = 1;
for (int i = 1; i < 2 * MAX_N; i++)
{
base1[i] = (base1[i - 1] * BASE1) % MOD1;
}
for (int i = 1; i <= 2 * n; i++)
{
hash1[i] = (hash1[i - 1] * BASE1 + s[i]) % MOD1;
}
for (int i = 2 * n; i >= 1; i--)
{
hash2[i] = (hash2[i + 1] * BASE1 + s[i]) % MOD1;
}
}
void work()
{
for (int i = 1; i <= n; i++)
{
// xx
// cout << "[" << 1 << " " << i << "] " << getHash1(1, i) << " " << "[" << i + n + 1 << " " << 2 * n << "] " << getHash1(i + n + 1, 2 * n) << "\n";
long long a = (getHash1(1, i) * base1[n - i] % MOD1 + getHash1(i + n + 1, 2 * n)) % MOD1;
// cout << "[" << i + 1 << " " << i + n << "] " << getHash2(i + 1, i + n) << "\n";
long long b = getHash2(i + 1, i + n) % MOD1;
// cout << i << " " << a << " " << b << "\n";
// cout << i << " " << a << " " << b << "\n";
if (a == b)
{
ans = i;
break;
}
}
}
void output()
{
if (ans == 0)
{
cout << "-1\n";
return;
}
for (int i = 1; i <= ans; i++)
cout << s[i];
for (int i = ans + n + 1; i <= 2 * n; i++)
cout << s[i];
cout << "\n";
cout << ans << "\n";
}
int main()
{
input();
init();
work();
output();
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 8ms
memory: 16932kb
input:
1000 baaaabaaaabbbabbabaaabbaaabbaaaabaabbabaabbabaaabaabbabaababbabaaababbabbaababbbbaaabaaababaaba...
output:
baaaabaaaabbbabbabaaabbaaabbaaaabaabbabbbbbbaabababaabaabababaababbbabbabbbaaaaaabaabbaaaabbaaaabbaa...
result:
ok 2 lines
Test #2:
score: 10
Accepted
time: 5ms
memory: 16928kb
input:
1000 cijgifeffcgefgccajhciabgghdabijcgbfahfgibeegdadcdcjfgbcddggjjccjefcfebeaeihadbfdhbiffedeecjgfid...
output:
cijgifeffcgefgccajhciabgghdabijcgbfahfgibeegdadcdcjfgbcddggjjccjefcfebeaeihadbfdhbiffedeecjgfidchagj...
result:
ok 2 lines
Test #3:
score: 10
Accepted
time: 8ms
memory: 16928kb
input:
1000 brbtpgkdddrqqdddqmuqzysquhnjswmlyslmpxmevvmvtjssgeamknjpgvnyqpwogfwlszttbxcqcgibybuevbpdyqmtmad...
output:
brbtpgkdddrqqdddqmuqzysquhnjswmlyslmpxmevvmvtjssgeamknjpgvnyqpwogfwlszttbxcqcgibybuevbpdyqmtmadocizt...
result:
ok 2 lines
Test #4:
score: 10
Accepted
time: 115ms
memory: 50012kb
input:
1000000 iwjdxdpyhuvlbzcfukcorctqgxgnfmgcmgywuhthdedqwwocmuyielbqbchzrwnurvaudtteccpbpiluuugmprkhzupi...
output:
iwjdxdpyhuvlbzcfukcorctqgxgnfmgcmgywuhthdedqwwocmuyielbqbchzrwnurvaudtteccpbpiluuugmprkhzupiuhrlbaib...
result:
ok 2 lines
Test #5:
score: 10
Accepted
time: 92ms
memory: 50012kb
input:
1000000 kjqzxxkdmrehayxxerhvfyhfcyqpqzjagcpijmyabluaoevkfnsazkslebqvpexnuobhovagnqzdbbtqbkdokcnkhfrn...
output:
kjqzxxkdmrehayxxerhvfyhfcyqpqzjagcpijmyabluaoevkfnsazkslebqvpexnuobhovagnqzdbbtqbkdokcnkhfrnfppgeglm...
result:
ok 2 lines
Test #6:
score: 10
Accepted
time: 104ms
memory: 50016kb
input:
1000000 omaekkwpmsvrdwiamsxatwfoqywrealbdbmbvozyiaygkygbdoqyqvvdbrtixwxsxxbgzzzurkhaiuusjntqycpfqtkx...
output:
omaekkwpmsvrdwiamsxatwfoqywrealbdbmbvozyiaygkygbdoqyqvvdbrtixwxsxxbgzzzurkhaiuusjntqycpfqtkxjfveetzo...
result:
ok 2 lines
Test #7:
score: 10
Accepted
time: 97ms
memory: 50012kb
input:
1000000 mydhvukreubtmphalmzigbbbjlhftcgkrqwdijlzflyguyhmqzwtirdhtdejznqrokcidxcfjtjtapjalzviroezhdso...
output:
mydhvukreubtmphalmzigbbbjlhftcgkrqwdijlzflyguyhmqzwtirdhtdejznqrokcidxcfjtjtapjalzviroezhdsorlnneiil...
result:
ok 2 lines
Test #8:
score: 10
Accepted
time: 97ms
memory: 50012kb
input:
1000000 cacbbcaaaccabccbbaacabcaaacaaaaaccaabababacbacaacbccbacaaacaacbbbbcacccbbabcbbcbbacabbacbabb...
output:
cacbbcaaaccabccbbaacabcaaacaaaaaccaabababacbacaacbccbacaaacaacbbbbcacccbbabcbbcbbacabbacbabbaccaacac...
result:
ok 2 lines
Test #9:
score: 10
Accepted
time: 107ms
memory: 50012kb
input:
1000000 ababaaaaabaabbbababaabababbabbabbaababababababababbbbababaaababbaabbababbbbababaabbaaababaaa...
output:
ababaaaaabaabbbababaabababbabbabbaababababababababbbbababaaababbaabbababbbbababaabbaaababaaabaababbb...
result:
ok 2 lines
Test #10:
score: 10
Accepted
time: 69ms
memory: 50012kb
input:
1000000 abbbbbabbaababaaabaababbbbbbaabaaaaaabbbbabbbbaaaaabbbbaaabbabbabaabaabbaabbaabaaaaaaababbba...
output:
-1
result:
ok single line: '-1'
Extra Test:
score: 0
Extra Test Passed