제출 #547264

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
547264		Jomnoi	세 명의 친구들 (BOI14_friends)	C++17	0 / 100	42 ms	33548 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 + 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;
}

컴파일 시 표준 에러 (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