Submission #744608

#	Time	Username	Problem	Language	Result	Execution time	Memory
744608		Valera_Grinenko	Three Friends (BOI14_friends)	C++17	100 / 100	222 ms	86424 KiB

friends

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#ifdef __APPLE__

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <immintrin.h>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>

#else
#include <bits/stdc++.h>
#endif

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#if __APPLE__
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl

template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }

#else
#define D while (false)
#define LOG(...)
#endif

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

bool is_prime(int number) {
    if (number <= 1) {
        return false;
    }
    for (int i = 2; i * i <= number; ++i) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}

int next_prime(int number) {
    for (int i = number + 1; ; ++i) {
        if (is_prime(i)) {
            return i;
        }
    }
}

const int seed = chrono::steady_clock::now().time_since_epoch().count();
mt19937 generator(seed);

int rnd() {
    return generator() >> 1;
}

int rnd(int r) {
    return rnd() % r;
}

int rnd(int l, int r) {
    return l + rnd(r - l + 1);
}

const int DEFAULT_BASE[] = {next_prime(300 + rnd(5000)),
                            next_prime(300 + rnd(5000))};
const int DEFAULT_MOD = next_prime(1000000000 + rnd(100000));

class HashInt {
public:
    HashInt() {
    }

    HashInt(const string &s, char min_c = 'a', int
    base = DEFAULT_BASE[0], int mod = DEFAULT_MOD): mod(mod), h(s.length()), pw(s.length()) {

        pw[0] = 1;
        for (int i = 1; i < s.length(); ++i) {
            pw[i] = (1LL * pw[i - 1] * base) % mod;
        }
        h[0] = s[0] - min_c + 1;
        for (int i = 1; i < s.length(); ++i) {
            h[i] = (1LL * h[i - 1] * base + s[i] - min_c + 1) % mod;
        }
    }

    int get_hash(int l, int r) const {
        if (!l) {
            return h[r];
        }
        return ((h[r] - 1LL * h[l - 1] * pw[r - l + 1]) % mod + mod) % mod;
    }

    int combine(int lhs, int rhs, int len_rhs) {
        return ((1ll * lhs * pw[len_rhs]) % mod + rhs) % mod;
    }

private:
    vector<int> h, pw;
    int mod;
};

class HashLong {
public:
    HashLong() {
    }

    HashLong(const string &s, char min_c = 'a', int base = DEFAULT_BASE[0]): h(s.length()), pw(s.length()) {
        pw[0] = 1;
        for (int i = 1; i < s.length(); ++i) {
            pw[i] = pw[i - 1] * base;
        }
        h[0] = s[0] - min_c + 1;
        for (int i = 1; i < s.length(); ++i) {
            h[i] = h[i - 1] * base + s[i] - min_c + 1;
        }
    }

    long long get_hash(int l, int r) const {
        if (!l) {
            return h[r];
        }
        return h[r] - h[l - 1] * pw[r - l + 1];
    }

    long long combine(long long lhs, long long rhs, int len_rhs) {
        return lhs * pw[len_rhs] + rhs;
    }

private:
    vector<long long> h, pw;
};

class Hash {
public:
    Hash() {
    }

    Hash(const string &s, char min_c = 'a',
         int base1 = DEFAULT_BASE[0], int base2 = DEFAULT_BASE[1],
         int mod = DEFAULT_MOD): h1(s, min_c, base1), h2(s, min_c, base2, mod) {
    }

    pair<long long, int> get_hash(int l, int r) {
        return {h1.get_hash(l, r), h2.get_hash(l, r)};
    }

    pair<long long, int> combine(pair<long long, int> lhs, pair<long long, int> rhs, int len_rhs) {
        return {h1.combine(lhs.fi, rhs.fi, len_rhs), h2.combine(lhs.se, rhs.se, len_rhs)};
    }

private:
    HashLong h1;
    HashInt h2;
};

void solve() {
    int n; cin >> n;
    string s; cin >> s;
    vector<pair<ll, ll> > hashes;
    int pos_delete = -1;
    if(n % 2 == 0) { cout << "NOT POSSIBLE\n"; return; }
    Hash h(s, 'A');
    int len = n / 2;
    if(h.get_hash(1, 1 + len - 1) == h.get_hash(1 + len, n - 1)) {
        hashes.pb(h.get_hash(1, 1 + len - 1));
        pos_delete = 0;
    }
    if(h.get_hash(0, len - 1) == h.get_hash(len + 1, n - 1)) {
        hashes.pb(h.get_hash(0, len - 1));
        pos_delete = len;
    }
    if(h.get_hash(0, len - 1) == h.get_hash(len, len + len - 1)) {
        hashes.pb(h.get_hash(0, len - 1));
        pos_delete = n - 1;
    }
    for(int i = 1; i < len; i++) {
        auto lhsh = h.combine(h.get_hash(0, i - 1), h.get_hash(i + 1, len), len - i);
        auto rhsh = h.get_hash(len + 1, n - 1);
        if(lhsh == rhsh) {
            pos_delete = i;
            hashes.pb(lhsh);
        }
    }
    for(int i = n - 2; i > n - len - 1; i--) {
        auto rhsh = h.combine(h.get_hash(n - len - 1, i - 1), h.get_hash(i + 1, n - 1), n - 1 - i);
        auto lhsh = h.get_hash(0, len - 1);
        if(lhsh == rhsh) {
            pos_delete = i;
            hashes.pb(lhsh);
        }
    }
    sort(all(hashes)); hashes.resize(unique(all(hashes)) - hashes.begin());
    if(len(hashes) == 0) cout << "NOT POSSIBLE\n";
    else if(len(hashes) == 1) {
        string ans;
        for(int i = 0; i < n && len(ans) < n / 2; i++)
            if(i != pos_delete) ans.pb(s[i]);
        cout << ans << '\n';
    } else cout << "NOT UNIQUE";
}

signed main() {
//   freopen("input.txt", "r", stdin);
//   freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;

    //cin >> t;

    while (t--) solve();

}

/*
KIVI
*/

Compilation message (stderr)

friends.cpp: In constructor 'HashInt::HashInt(const string&, char, int, int)':
friends.cpp:159:9: warning: 'HashInt::mod' will be initialized after [-Wreorder]
  159 |     int mod;
      |         ^~~
friends.cpp:158:17: warning:   'std::vector<int> HashInt::h' [-Wreorder]
  158 |     vector<int> h, pw;
      |                 ^
friends.cpp:133:5: warning:   when initialized here [-Wreorder]
  133 |     HashInt(const string &s, char min_c = 'a', int
      |     ^~~~~~~
friends.cpp:137:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |         for (int i = 1; i < s.length(); ++i) {
      |                         ~~^~~~~~~~~~~~
friends.cpp:141:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |         for (int i = 1; i < s.length(); ++i) {
      |                         ~~^~~~~~~~~~~~
friends.cpp: In constructor 'HashLong::HashLong(const string&, char, int)':
friends.cpp:169:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |         for (int i = 1; i < s.length(); ++i) {
      |                         ~~^~~~~~~~~~~~
friends.cpp:173:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |         for (int i = 1; i < s.length(); ++i) {
      |                         ~~^~~~~~~~~~~~

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