Submission #547262

#	Time	Username	Problem	Language	Result	Execution time	Memory
547262		Jomnoi	Three Friends (BOI14_friends)	C++17	0 / 100	72 ms	36560 KiB

friends

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

const int MAX_N = 2e6 + 10;
const int P = 31;
const int MOD = 1e9 + 9;

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

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] = (divide[i - 1] * P) % MOD;
        Hash[i] = (Hash[i - 1] * P + (S[i] - 'A' + 1)) % MOD;
    }

    vector <int> ans;
    long long H1, H2;
    for(int i = 1; i <= n; i++) {
        if(i - 1 <= N)
        H1 = Hash[i - 1] * divide[n - i + 1];
        H1 += Hash[n + 1] - Hash[i] * divide[n - i + 1];
        H1 = (H1 % MOD + MOD) % MOD;

        H2 = Hash[N] - Hash[n + 1] * divide[n];
        H2 = (H2 % MOD + MOD) % MOD;

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

        H2 = (Hash[i - 1] - Hash[n] * divide[i - n - 1]) * divide[N - i];
        H2 += Hash[N] - Hash[i] * divide[N - i];
        H2 = (H2 % MOD + MOD) % MOD;

        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;
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:34:12: warning: 'H1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   34 |         H1 += Hash[n + 1] - Hash[i] * divide[n - i + 1];
      |         ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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