要不你还是把我删了吧

博客标题 / 2024-09-25 / 原文

A. 3 idots

http://222.180.160.110:61234/contest/5556/problem/1

你会发现有两种情况：多余字符在前 / 后。

你拿后面的去匹配前面的，再拿前面的去匹配后面的，如果匹配出来有多解就 NOT UNIQUE，无解就 NOT POSSIBLE，有解就输出。

#include <bits/stdc++.h>
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    freopen("string.in", "r", stdin);
    freopen("string.out", "w", stdout);
    int n;
    static char t[2000005];
    std::cin >> n >> (t + 1);
    if (n % 2 == 0)
        std::cout << "NOT POSSIBLE\n";
    else {
        int p1, q1, p2, q2, i;
        for (i = 0, p1 = n / 2; i < n / 2 && t[i + 1] == t[p1 + 1]; ++i, ++p1);
        for (i = n / 2 + 1, q1 = n + 1; i > 1 && t[i - 1] == t[q1 - 1]; --i, --q1);
        for (i = n / 2 + 1, p2 = 0; i < n && t[i + 1] == t[p2 + 1]; ++i, ++p2);
        for (i = n + 1, q2 = n / 2 + 2; i > n / 2 + 2 && t[i - 1] == t[q2 - 1]; --i, --q2);
        // printf("p1 = %d, q1 = %d; p2 = %d, q2 = %d\n", p1, q1, p2, q2);
        if (p1 >= q1 - 2 && p2 >= q2 - 2 && [&]() -> bool {
            for (int i = 1, j = n / 2 + 2; i <= n / 2; ++i, ++j) {
                if (t[i] != t[j])
                    return 1;
            }
            return 0;
        }())
            std::cout << "NOT UNIQUE\n";
        else if (p1 < q1 - 2 && p2 < q2 - 2)
            std::cout << "NOT POSSIBLE\n";
        else if (p1 >= q1 - 2) {
            for (i = 1; i <= n / 2; ++i)
                std::cout << t[i];
            std::cout << '\n';
        }
        else {
            for (int i = n / 2 + 2; i <= n; ++i)
                std::cout << t[i];
            std::cout << '\n';
        }
    }
    return 0;
}