Submission #845121

#	Time	Username	Problem	Language	Result	Execution time	Memory
845121		vuavisao	Three Friends (BOI14_friends)	C++17	100 / 100	208 ms	52804 KiB

friends

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define ll long long
using namespace std;

const int N = 2e6 + 10;

const uint8_t size_T = 2;
const int _1hrd = 100;
const int _1bil = 1000000000;
const array<int, size_T> MOD = {_1bil + 9, _1bil + 11};
const array<int, size_T> BASE = {_1hrd + 28, _1hrd + 31};

struct Hash {
    array<int, size_T> val = {0};
    Hash() {};
    Hash (int x) {
        for (uint8_t i = 0; i < size_T; ++ i)
            this -> val[i] = x % MOD[i];
    }

    bool operator < (const Hash& other) const {
        for (uint8_t i = 0; i < size_T; ++ i)
            if (this -> val[i] != other.val[i]) return this -> val[i] < other.val[i];
        return false;
    }

    bool operator == (const Hash& other) const {
        for (uint8_t i = 0; i < size_T; ++ i)
            if (this -> val[i] != other.val[i]) return false;
        return true;
    }

    Hash operator + (const int& x) const {
        Hash res;
        for (uint8_t i = 0; i < size_T; ++ i)
            res.val[i] = (1ll * this -> val[i] * BASE[i] + x) % MOD[i];
        return res;
    }

    Hash operator + (const Hash& other) const {
        Hash res;
        for (uint8_t i = 0; i < size_T; ++ i) {
            // res.val[i] = (this -> val[i] + other.val[i]) % MOD[i];
            res.val[i] = (this -> val[i] + other.val[i]);
            res.val[i] = res.val[i] + (res.val[i] < 0) * MOD[i] - (res.val[i] >= MOD[i]) * MOD[i];
        }   
        return res;
    }

    Hash operator - (const Hash& other) const {
        Hash res;
        for (uint8_t i = 0; i < size_T; ++ i) {
            // res.val[i] = (this -> val[i] - other.val[i]) % MOD[i];
            // res.val[i] = (res.val[i] + MOD[i]) % MOD[i];
            res.val[i] = (this -> val[i] - other.val[i]);
            res.val[i] = res.val[i] + (res.val[i] < 0) * MOD[i] - (res.val[i] >= MOD[i]) * MOD[i];
        }
        return res;
    }

    Hash operator * (const Hash& other) const {
        Hash res;
        for (uint8_t i = 0; i < size_T; ++ i)
            res.val[i] = (1ll * this -> val[i] * other.val[i]) % MOD[i];
        return res;
    }

    friend ostream& operator << (ostream& os, Hash& other) {
        os << "[ ";
        for (uint8_t i = 0; i < size_T; ++ i) {
            os << other.val[i];
            if(i < size_T - 1) os << ',';
            os << ' ';
        }
        os << "]";
        return os;
    }
};

int n;
string s;

Hash p[N], h[N];

Hash get_hash(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    p[0] = 1; for(int i = 1; i <= 2000001; ++ i) p[i] = p[i - 1] + 0;
    cin >> n >> s; s = ' ' + s;
    for(int i = 1; i <= n; ++ i) h[i] = h[i - 1] + s[i];
    if(!(n & 1)) {
        cout << "NOT POSSIBLE";
        return 0;
    }
    vector<Hash> List = {};
    int idx_dif = - 1;
    int len = n / 2;
    for(int i = 1; i <= n; ++ i) {
        if(i <= len) {
            int bonus = len - (i - 1);
            if(get_hash(1, i - 1) * p[bonus] + get_hash(i + 1, i + 1 + bonus - 1) == get_hash(i + 1 + bonus, n)) {
                List.push_back(get_hash(i + 1 + bonus, n));
                idx_dif = i;
            }
        }
        else if(i > len + 1) {
            if(get_hash(1, len) == get_hash(len + 1, i - 1) * p[n - (i + 1) + 1] + get_hash(i + 1, n)) {
                List.push_back(get_hash(1, len));
                idx_dif = i;
            }
        }
        else {
            if(get_hash(1, len) == get_hash(len + 2, n)) {
                List.push_back(get_hash(1, len));
                idx_dif = i;
            }
        }
    }
    sort(List.begin(), List.end());
    List.resize(unique(List.begin(), List.end()) - List.begin());
    // cerr << cnt_can_dif << '\n';
    if((int) List.size() == 0) {
        cout << "NOT POSSIBLE";
    }
    else if((int) List.size() > 1) {
        cout << "NOT UNIQUE";
    }
    else {
        for(int i = 1; len > 0; ++ i) {
            if(i == idx_dif) continue;
            -- len;
            cout << s[i];
        }   
    }
    return (0 ^ 0);
}

/// Code by vuavisao

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