Submission #547269

#	Time	Username	Problem	Language	Result	Execution time	Memory
547269		Jomnoi	Three Friends (BOI14_friends)	C++17	0 / 100	152 ms	67928 KiB

friends

#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;

const int MAX_N = 2e6 + 10;
const long long P1 = 53;
const long long P2 = 97;
const long long MOD1 = 1e9 + 9;
const long long MOD2 = 1e9 + 7;

char S[MAX_N];
long long Hash1[MAX_N], Hash2[MAX_N];
long long divide1[MAX_N], divide2[MAX_N];

long long add(const long long &a, const long long &b, const long long &m) {
    return ((a % m) + (b % m)) % m;
}

long long subtract(const long long &a, const long long &b, const long long &m) {
    return (((a % m) - (b % m)) % m + m) % m;
}

long long multiply(const long long &a, const long long &b, const long long &m) {
    return (a % m) * (b % m) % m;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int N;
    cin >> N >> (S + 1);
    if(N % 2 == 0) {
        cout << "NOT POSSIBLE";
        return 0;
    }

    int n = (N - 1) / 2;
    divide1[0] = 1;
    divide2[0] = 1;
    for(int i = 1; i <= N; i++) {
        divide1[i] = multiply(divide1[i - 1], P1, MOD1);
        divide2[i] = multiply(divide2[i - 1], P2, MOD2);
        Hash1[i] = add(multiply(Hash1[i - 1], P1, MOD1), (S[i] - 'A' + 1), MOD1);
        Hash2[i] = add(multiply(Hash2[i - 1], P2, MOD2), (S[i] - 'A' + 1), MOD2);
    }

    vector <int> ans;
    long long H11, H12, H21, H22;
    for(int i = 1; i <= n; i++) {
        H11 = multiply(Hash1[i - 1], divide1[n - i + 1], MOD1);
        H11 = add(H11, subtract(Hash1[n + 1], multiply(Hash1[i], divide1[n - i + 1], MOD1), MOD1), MOD1);
        H12 = multiply(Hash2[i - 1], divide2[n - i + 1], MOD2);
        H12 = add(H12, subtract(Hash2[n + 1], multiply(Hash2[i], divide2[n - i + 1], MOD2), MOD2), MOD2);

        H21 = subtract(Hash1[N], multiply(Hash1[n + 1], divide1[n], MOD1), MOD1);
        H22 = subtract(Hash2[N], multiply(Hash2[n + 1], divide2[n], MOD2), MOD2);

        if(make_pair(H11, H12) == make_pair(H21, H22)) {
            ans.push_back(i - 1);
        }
    }
    for(int i = n + 1; i <= N; i++) {
        H11 = Hash1[n];
        H12 = Hash2[n];

        H21 = multiply(subtract(Hash1[i - 1], multiply(Hash1[n], divide1[i - n - 1], MOD1), MOD1), divide1[N - i], MOD1);
        H21 = add(H21, subtract(Hash1[N], multiply(Hash1[i], divide1[N - i], MOD1), MOD1), MOD1);
        H22 = multiply(subtract(Hash2[i - 1], multiply(Hash2[n], divide2[i - n - 1], MOD2), MOD2), divide2[N - i], MOD2);
        H22 = add(H22, subtract(Hash2[N], multiply(Hash2[i], divide2[N - i], MOD2), MOD2), MOD2);

        if(make_pair(H11, H12) == make_pair(H21, H22)) {
            ans.push_back(n);
        }
    }

    if(ans.empty()) {
        cout << "NOT POSSIBLE";
    }
    else if(ans.size() > 1) {
        cout << "NOT UNIQUE";
    }
    else {
        for(int i = 1; i <= ans[0] and n--; i++) {
            cout << S[i];
        }
        for(int i = ans[0] + 2; n--; i++) {
            cout << S[i];
        }
    }
    return 0;
}

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