Submission #88719

#	Time	Username	Problem	Language	Result	Execution time	Memory
88719		popovicirobert	Three Friends (BOI14_friends)	C++14	100 / 100	90 ms	35260 KiB

friends

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const int MAXN = (int) 2e6;
const int B = 37;

char str[MAXN + 1];
ull hsh[MAXN + 1], pw[MAXN + 1];

inline ull get(int l, int r) {
    if(l > r)
        return 0;
    return hsh[r] - hsh[l - 1] * pw[r - l + 1];
}

inline void update(int st, int dr, int &l, int &r, ull &val) {
    if(l == 0) {
        l = st, r = dr, val = get(st, dr);
        return ;
    }
    ull cur = get(st, dr);
    if(cur != val) {
        cout << "NOT UNIQUE";
        exit(0);
    }
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> str + 1;
    if(n % 2 == 0) {
        cout << "NOT POSSIBLE";
        return 0;
    }
    pw[0] = 1;
    for(i = 1; i <= n; i++) {
        hsh[i] = hsh[i - 1] * B + str[i] - 'A' + 1;
        pw[i] = pw[i - 1] * B;
    }
    int len = (n - 1) / 2;
    int l = 0, r = 0;
    ull val;
    if(get(2, len + 1) == get(n - len + 1, n)) {
        update(2, len + 1, l, r, val);
    }
    if(get(n - len, n - 1) == get(1, len)) {
        update(n - len, n - 1, l, r, val);
    }
    for(i = 2; i < n; i++) {
        ull a, b;
        if(i <= len + 1) {
            a = get(1, i - 1) * pw[len - i + 1] + get(i + 1, len + 1);
            b = get(len + 2, n);
        }
        else {
            a = get(1, len);
            b = get(i + 1, n) + get(n - len, i - 1) * pw[n - i];
        }
        if(a == b) {
            if(i <= len + 1) {
                update(len + 2, n, l, r, val);
            }
            else {
                update(1, len, l, r, val);
            }
        }
    }
    if(l == 0) {
        cout << "NOT POSSIBLE";
        return 0;
    }
    for(i = l; i <= r; i++) {
        cout << str[i];
    }
    //cin.close();
    //cout.close();
    return 0;
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:40:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     cin >> n >> str + 1;
                 ~~~~^~~

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