UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#206090#3168. 解码tanghexuan100702ms50016kbC++112.6kb2024-07-20 19:36:442024-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