Submission #547266

#	Time	Username	Problem	Language	Result	Execution time	Memory
547266		Jomnoi	Three Friends (BOI14_friends)	C++17	0 / 100	66 ms	33824 KiB

friends

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

const int MAX_N = 2e6 + 10;
const int P = 31;
const long long MOD = 1e18 + 7;

char S[MAX_N];
long long Hash[MAX_N];
long long divide[MAX_N];

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

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

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

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;
    divide[0] = 1;
    for(int i = 1; i <= N; i++) {
        divide[i] = multiply(divide[i - 1], P);
        Hash[i] = add(multiply(Hash[i - 1], P), (S[i] - 'A' + 1));
    }

    vector <int> ans;
    long long H1, H2;
    for(int i = 1; i <= n; i++) {
        H1 = multiply(Hash[i - 1], divide[n - i + 1]);
        H1 = add(H1, subtract(Hash[n + 1], multiply(Hash[i], divide[n - i + 1])));

        H2 = subtract(Hash[N], multiply(Hash[n + 1], divide[n]));

        if(H1 == H2) {
            ans.push_back(i - 1);
        }
    }
    for(int i = n + 1; i <= N; i++) {
        H1 = Hash[n];

        H2 = multiply(subtract(Hash[i - 1], multiply(Hash[n], divide[i - n - 1])), divide[N - i]);
        H2 = add(H2, subtract(Hash[N], multiply(Hash[i], divide[N - i])));

        if(H1 == H2) {
            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