Submission #1014876

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014876		phoenix	Three Friends (BOI14_friends)	C++17	100 / 100	164 ms	83028 KiB

friends

#include <bits/stdc++.h>

using namespace std;


const int N = 2000010;
const int MOD = 1e9 + 9;

void norm(long long &x) { x = x % MOD + (x < 0) * MOD; }

struct H {
    using ll = long long;
    using ull = unsigned long long;
    
    static const int base1 = 147;
    static const int base2 = 191;
    static ll pw1[N];
    static ull pw2[N];
    static void init() {
        H::pw1[0] = H::pw2[0] = 1;
        for (int i = 1; i < N; i++) {
            H::pw1[i] = H::pw1[i - 1] * base1 % MOD;
            H::pw2[i] = H::pw2[i - 1] * base2;
        }  
    }

    ll h1;
    ull h2;
    int len;
    H () : h1(), h2(), len() {}
    H (char c) : len(1), h1(c), h2(c) {}
    H& operator += (const H &a) {
        len += a.len;
        h1 *= pw1[a.len]; 
        h1 += a.h1;
        norm(h1);
        h2 *= pw2[a.len]; 
        h2 += a.h2;
        return *this;
    }
};
long long H::pw1[];
unsigned long long H::pw2[];
H operator + (H a, const H b) {
    return a += b;
}
H operator - (const H a, const H b) {
    H res;
    res.len = a.len - b.len;
    res.h1 = a.h1 - b.h1 * H::pw1[res.len];
    res.h2 = a.h2 - b.h2 * H::pw2[res.len];
    // res.h1 = res.h1 % H::MOD + (res.h1 < 0) * H::MOD;
    norm(res.h1);
    return res;
}
bool operator == (const H a, const H b) { 
    return (a.len == b.len && a.h1 == b.h1 && a.h2 == b.h2); 
}
bool operator != (const H a, const H b) {return !(a == b); }

/*

a0 * x^3 + a1 * x^2 + a2 * x^1 + a3 * x^0
a0 * x^1 + a1 * x^0

*/

void print(H a) {
    cout << "{" << a.h1 << ' ' << a.h2 << ' ' << a.len << "}\n";
} 

int n;
char s[N];
H hsh[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    H::init();
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> s[i];
    if (~n & 1) {
        cout << "NOT POSSIBLE\n";
        return 0;
    }
    for (int i = 1; i <= n; i++)
        hsh[i] = hsh[i - 1] + H(s[i]);
    
    bool flag1 = false, flag2 = false;
    /*
    1234567
    */
    int m = n / 2;
   
    for (int i = 1; i <= m; i++) {
        H t;
        t += hsh[i - 1];
        t += (hsh[m + 1] - hsh[i]);
        if (t == (hsh[n] - hsh[m + 1])) 
            flag2 = true;
    }
    for (int i = m + 1; i <= n; i++) {
        H t; 
        t += hsh[i - 1] - hsh[m];
        t += hsh[n] - hsh[i];
        if (t == hsh[m]) 
            flag1 = true;
    }

    if (flag1 && flag2) {
        if (hsh[m] != (hsh[n] - hsh[m + 1])) {
            cout << "NOT UNIQUE\n";
            return 0;
        }
    }
    if (flag1) 
        for (int i = 1; i <= m; i++) cout << s[i];
    else {
        if (flag2) 
            for (int i = m + 2; i <= n; i++) cout << s[i];
        else 
            cout << "NOT POSSIBLE";
    }
    cout << '\n';
}

Compilation message (stderr)

friends.cpp: In constructor 'H::H(char)':
friends.cpp:29:9: warning: 'H::len' will be initialized after [-Wreorder]
   29 |     int len;
      |         ^~~
friends.cpp:27:8: warning:   'H::ll H::h1' [-Wreorder]
   27 |     ll h1;
      |        ^~
friends.cpp:31:5: warning:   when initialized here [-Wreorder]
   31 |     H (char c) : len(1), h1(c), h2(c) {}
      |     ^

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