Submission #527557

#	Time	Username	Problem	Language	Result	Execution time	Memory
527557		jalsol	Three Friends (BOI14_friends)	C++11	100 / 100	93 ms	20852 KiB

friends

#include <bits/stdc++.h>

using namespace std;

#define Task ""

struct __Init__ {
    __Init__() {
        cin.tie(nullptr)->sync_with_stdio(false);
        if (fopen(Task".inp", "r")) {
            freopen(Task".inp", "r", stdin);
            freopen(Task".out", "w", stdout); }
    }
} __init__;

using ll = long long;

#ifdef LOCAL
#define debug(x) cerr << "[" #x " = " << x << "]\n";
#else
#define debug(...)
#endif // LOCAL

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fi first
#define se second

#define For(i, l, r) for (int i = (l); i <= (r); ++i)
#define Ford(i, r, l) for (int i = (r); i >= (l); --i)
#define Rep(i, n) For (i, 0, (n) - 1)
#define Repd(i, n) Ford (i, (n) - 1, 0)

template<class C> int isz(const C& c) { return c.size(); }
template<class T> bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }

constexpr int eps = 1e-9;
constexpr int inf = 1e9;
constexpr ll linf = 1e18;

// =============================================================================

constexpr int maxN = 2e6 + 5;
constexpr int base = 31;

struct mint {
    int v;
    static constexpr int mod = 1e9 + 123;

    mint() : v() {}
    mint(ll _v) : v(_v % mod) { v += mod * (v < 0); }

    mint& operator+=(const mint& o) {
        if ((v += o.v) >= mod) v -= mod;
        return *this;
    }
    mint& operator-=(const mint& o) {
        if ((v -= o.v) < 0) v += mod;
        return *this;
    }
    mint& operator*=(const mint& o) {
        return *this = mint(1LL * v * o.v);
    }

    friend mint operator+(const mint& a, const mint& b) {
        return mint(a) += b;
    }
    friend mint operator-(const mint& a, const mint& b) {
        return mint(a) -= b;
    }
    friend mint operator*(const mint& a, const mint& b) {
        return mint(a) *= b;
    }
};

int n;
char s[maxN];
mint hs[maxN];
mint pw[maxN];

mint getHash(int l, int r) {
    return hs[r] - hs[l - 1] * pw[r - l + 1];
}

signed main() {
    cin >> n >> (s + 1);

    pw[0] = 1;
    For (i, 1, n) {
        pw[i] = pw[i - 1] * base;
    }

    For (i, 1, n) {
        hs[i] = hs[i - 1] * base + (s[i] - 'A' + 1);
    }

    mint ans = 0;
    int ansL, ansR;
    int mid = n / 2 + 1;

    For (i, 1, n) {
        // 1..i-1 + i+1..n/2+1
        mint pat, txt;
        int l, r;

        if (i < mid) {
            pat = getHash(mid + 1, n);
            txt = getHash(1, i - 1) * pw[mid - i] + getHash(i + 1, mid);
            l = mid + 1, r = n;
        } else {
            pat = getHash(1, mid - 1);
            txt = getHash(mid, i - 1) * pw[n - i] + getHash(i + 1, n);
            l = 1, r = mid - 1;
        }


        if (pat.v == txt.v) {
            if (!ans.v) {
                ans = pat;
                ansL = l;
                ansR = r;
            } else if (ans.v != pat.v) {
                cout << "NOT UNIQUE\n";
                return 0;
            }
        }
    }

    if (ans.v == 0) {
        cout << "NOT POSSIBLE\n";
    } else {
        For (i, ansL, ansR) cout << s[i];
        cout << '\n';
    }
}

/*

*/

Compilation message (stderr)

friends.cpp: In constructor '__Init__::__Init__()':
friends.cpp:11:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |             freopen(Task".inp", "r", stdin);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
friends.cpp:12:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |             freopen(Task".out", "w", stdout); }
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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