Submission #98426

#	Time	Username	Problem	Language	Result	Execution time	Memory
98426		Kastanda	Three Friends (BOI14_friends)	C++11	100 / 100	189 ms	20984 KiB

friends

#include<bits/stdc++.h>
using namespace std;
const int N = 2000009, Mod = 1e9 + 9;
int n, P[N], H[N];
char A[N];
inline int GetHash(int l, int r)
{
    return (H[r] - H[l - 1] * 1LL * P[r - l + 1] % Mod + Mod) % Mod;
}
int main()
{
    scanf("%d%s", &n, A + 1);
    if (n % 2 == 0)
        return !printf("NOT POSSIBLE\n");
    for (int i = P[0] = 1; i < N; i++)
        P[i] = P[i - 1] * 791LL % Mod;
    for (int i = 1; i <= n; i++)
        H[i] = (H[i - 1] + A[i]) * 791LL % Mod;
    int len = n >> 1, HSH = -1;
    for (int i = 1; i <= n; i++)
    {
        int hsh1, hsh2;
        if (i <= len)
        {
            hsh1 = (GetHash(1, i - 1) * 1LL * P[len - (i - 1)] + GetHash(i + 1, len + 1)) % Mod;
            hsh2 = GetHash(n - len + 1, n);
        }
        else
        {
            hsh1 = GetHash(1, len);
            hsh2 = (GetHash(len + 1, i - 1) * 1LL * P[len - (i - len - 1)] + GetHash(i + 1, n)) % Mod;
        }
        if (hsh1 != hsh2)
            continue;
        if (HSH == -1)
            HSH = hsh1;
        if (hsh1 != HSH)
            return !printf("NOT UNIQUE\n");
    }
    for (int i = 1; i <= n; i++)
        if (GetHash(i, i + len - 1) == HSH)
        {
            A[i + len] = 0;
            printf("%s\n", A + i);
            return 0;
        }
    return !printf("NOT POSSIBLE\n");
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%s", &n, A + 1);
     ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 35 / 35
• Subtask 2: 65 / 65