Submission #1150230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150230		The_Samurai	Three Friends (BOI14_friends)	C++20	100 / 100	180 ms	49384 KiB

friends

// I stand with PALESTINE



//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2")

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
//using namespace __gnu_pbds;

#define int long long
#define ff first
#define ss second
#define sz(a) (int) (a).size()
//template<class T, class C = null_type> using ordered_tree = tree<T, C, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long double ld;

namespace io {

    template<typename F, typename S>
    ostream &operator<<(ostream &os, const pair<F, S> &p) { return os << p.ff << " " << p.ss; }

    template<typename F, typename S>
    ostream &operator<<(ostream &os, const map<F, S> &mp) {
        for (auto it: mp) { os << it << endl; }
        return os;
    }

    template<typename F>
    ostream &operator<<(ostream &os, const vector<F> &v) {
        bool space = false;
        for (F x: v) {
            if (space) os << " ";
            space = true;
            os << x;
        }
        return os;
    }

    template<typename F>
    ostream &operator<<(ostream &os, const deque<F> &d) {
        bool space = false;
        for (F x: d) {
            if (space) os << " ";
            space = true;
            os << x;
        }
        return os;
    }

    template<typename F>
    ostream &operator<<(ostream &os, const set<F> &st) {
        bool space = false;
        for (F x: st) {
            if (space) os << " ";
            space = true;
            os << x;
        }
        return os;
    }

    template<typename F>
    ostream &operator<<(ostream &os, const multiset<F> &st) {
        bool space = false;
        for (F x: st) {
            if (space) os << " ";
            space = true;
            os << x << x;
        }
        return os;
    }

    template<typename F, typename S>
    istream &operator>>(istream &is, pair<F, S> &p) { return is >> p.ff >> p.ss; }

    template<typename F>
    istream &operator>>(istream &is, vector<F> &v) {
        for (F &x: v) { is >> x; }
        return is;
    }

    long long fastread() {
        char c;
        long long d = 1, x = 0;
        do c = getchar(); while (c == ' ' || c == '\n');
        if (c == '-') c = getchar(), d = -1;
        while (isdigit(c)) {
            x = x * 10 + c - '0';
            c = getchar();
        }
        return d * x;
    }

    static bool sep = false;

    using std::to_string;

    string to_string(bool x) {
        return (x ? "true" : "false");
    }

    string to_string(const string &s) { return "\"" + s + "\""; }

    string to_string(const char *s) { return "\"" + string(s) + "\""; }

    string to_string(const char &c) {
        string s;
        s += c;
        return "\'" + s + "\'";
    }

    template<typename Type>
    string to_string(vector<Type>);

    template<typename F, typename S>
    string to_string(pair<F, S>);

    template<typename Collection>
    string to_string(Collection);

    template<typename F, typename S>
    string to_string(pair<F, S> p) { return "{" + to_string(p.ff) + ", " + to_string(p.ss) + "}"; }

    template<typename Type>
    string to_string(vector<Type> v) {
        bool sep = false;
        string s = "[";
        for (Type x: v) {
            if (sep) s += ", ";
            sep = true;
            s += to_string(x);
        }
        s += "]";
        return s;
    }

    template<typename Collection>
    string to_string(Collection collection) {
        bool sep = false;
        string s = "{";
        for (auto x: collection) {
            if (sep) s += ", ";
            sep = true;
            s += to_string(x);
        }
        s += "}";
        return s;
    }

    void print() {
        cout << endl;
        sep = false;
    }

    template<typename F, typename... Other>
    void print(F ff, Other... other) {
        if (sep) cout << " | ";
        sep = true;
        cout << to_string(ff);
        print(other...);
    }

}
using namespace io;

namespace utils {

    template<typename F, typename S>
    inline void maxs(F &a, S b) { a = a > b ? a : b; }

    template<typename F, typename S>
    inline void mins(F &a, S b) { a = a < b ? a : b; }

    template<typename F, typename S>
    long long max(F a, S b) { return a > b ? a : b; }

    template<typename F, typename S>
    long long min(F a, S b) { return a < b ? a : b; }

    constexpr long long operator "" _E(unsigned long long n) {
        long long p = 1, a = 10;
        for (int i = 0; i < n; i++) p *= a;
        return p;
    }

    random_device rd;
    mt19937 mt(rd());

    template<typename T>
    T rand(T l, T r) {
        uniform_int_distribution<T> dist(l, r);
        return dist(mt);
    };

}
using namespace utils;


#ifdef sunnatov
#define print(...) cout << "[" << #__VA_ARGS__ << "]: "; io::print( __VA_ARGS__ );
#else
#define print( ... ) 42
#endif

const double EPS = 1e-7;
long long doxuya = 18_E + 10;
int INF = 9_E + 10;
const char nl = '\n';

int month[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

/*

*/

vector<int> primes_list = {993146723,996752089,993912011,993276811,990439561,999134321,1000034863,990310561,1002852971,990902071,1002552547,1004791829,1006000901,1000242487,998810363,998510393,1005429353,1006591627,1007173513,1001089151,1007873257,1002742243,997222561,995034571,993148837,1007335169,1007688763,1000458911,995690771,1000963499,1004540941,996669341,1009791163,1005362731,990259279,1004949923,999257549,994083157,997000859,991488709,990129697,991686341,1006200047,995269721,998938153,1001274091,1008215713,1005259139,990913177,1000705361,992677943,1001761259,1008933127,991650763,1003413907,1001591489,999972499,1001013547,996769511,1001061553,998571107,1005498281,1004864467,1008537151,995490059,994271963,1000330937,1007601659,999935701,1007473871,1005960979,1009408901,1003306259,1001731277,993759673,1005202493,994289501,992293103,1007638627,991446553,991299677,1007753729,1003063247,1008357107,995452751,995169853,993065287,1009534639,991566083,995628827,992550289,993078701,1009667231,996338407,996761473,1008855797,1005879461,1000745609,997377253,1000759181};
int base, mod;
vector<int> modPow;

struct __hash {
    vector<int> h;
 
    inline void init(const vector<int> &a) {
        if (base == 0) {
            mt19937 rngHash(chrono::high_resolution_clock::now().time_since_epoch().count());
            mod = primes_list[rngHash() % (int) primes_list.size()];
            base = rngHash() % (mod - 2) + 2;
        }
        
        int n = (int) a.size();
        h.resize(n);
        
        int sz = (int) modPow.size();
        if (sz <= n) {
            modPow.resize(n + 1);
            modPow[0] = 1;
            for (int i = max(1, sz); i <= n; i++)
                modPow[i] = 1ll * modPow[i - 1] * base % mod;
        }

        for (int i = 0; i < n; i++) {
            h[i] = a[i] % mod;
            if (i > 0) h[i] = (1ll * h[i - 1] * base + h[i]) % mod;
        }
    }
 
    inline void init(const string &s) {
        int n = (int) s.size();
        vector<int> a(n);
        for (int i = 0; i < n; i++) a[i] = (int) s[i];
        init(a);
    }
 
    inline int get(int l, int r) {
        assert(l <= r);
        int res = h[r];
        if (l > 0){
            res -= (long long) modPow[r - l + 1] * h[l - 1] % mod;
            if (res < 0) res += mod;
        }
        return res;
    }

    inline bool same(int l1, int r1, int l2, int r2) {
        return get(l1, r1) == get(l2, r2);
    }
};

void solution(istream &cin, ostream &cout, const int &test_case) {
    int n;
    string s;
    cin >> n >> s;
    if (n % 2 == 0) {
        cout << "NOT POSSIBLE";
        return;
    }
    __hash hsh; hsh.init(s);
    auto [la, ra] = make_pair(-1, -1);
    for (int i = 0; i < n; i++) {
        vector<pair<int, int>> ranges;
        if (i) ranges.emplace_back(0, i - 1);
        if (i + 1 < n) ranges.emplace_back(i + 1, n - 1);
        sort(ranges.begin(), ranges.end(), [&](pair<int, int> a, pair<int, int> b) {
            return a.ss - a.ff > b.ss - b.ff;
        });
        if (sz(ranges) == 1) {
            auto [l, r] = ranges[0];
            if (hsh.get(l, (l + r) / 2) != hsh.get((l + r) / 2 + 1, r)) continue;
            if (la == -1) la = l, ra = (l + r) / 2;
            else if (hsh.get(la, ra) != hsh.get(l, (l + r) / 2)) {
                cout << "NOT UNIQUE";
                return;
            }
            continue;
        }
        auto [l, r] = ranges[0];
        if (r == n - 1 and (r - l + 1) > n / 2) {
            ranges.erase(ranges.begin());
            ranges.emplace_back(r - n / 2 + 1, r);
            ranges.emplace_back(l, r - n / 2);
        } else if ((r - l + 1) > n / 2) {
            ranges.erase(ranges.begin());
            ranges.emplace_back(l, l + n / 2 - 1);
            ranges.emplace_back(l + n / 2, r);
        }
        if (sz(ranges) == 2) {
            auto [l, r] = ranges[0];
            if (hsh.get(l, r) != hsh.get(ranges[1].ff, ranges[1].ss)) continue;
            if (la == -1) tie(la, ra) = ranges[0];
            else if (hsh.get(la, ra) != hsh.get(l, r)) {
                cout << "NOT UNIQUE";
                return;
            }
            continue;
        }
        sort(ranges.begin(), ranges.end());
        print(i, ranges);
        if (ranges[0].ss - ranges[0].ff > ranges[2].ss - ranges[2].ff) {
            int ln = ranges[1].ss - ranges[1].ff + 1;
            bool ok = hsh.get(0, ln - 1) == hsh.get(ranges[1].ff, ranges[1].ss);
            ok &= hsh.get(ln, ranges[0].ss) == hsh.get(ranges[2].ff, ranges[2].ss);
            if (!ok) continue;
            if (la == -1) tie(la, ra) = ranges[0];
            else if (hsh.get(la, ra) != hsh.get(ranges[0].ff, ranges[0].ss)) {
                cout << "NOT UNIQUE";
                return;
            }
        } else {
            int ln = ranges[0].ss - ranges[0].ff + 1;
            print(ranges[2].ff, ranges[2].ff + ln - 1);
            bool ok = hsh.get(ranges[2].ff, ranges[2].ff + ln - 1) == hsh.get(ranges[0].ff, ranges[0].ss);
            ok &= hsh.get(ranges[2].ff + ln, ranges[2].ss) == hsh.get(ranges[1].ff, ranges[1].ss);
            if (!ok) continue;
            if (la == -1) tie(la, ra) = ranges[2];
            else if (hsh.get(la, ra) != hsh.get(ranges[2].ff, ranges[2].ss)) {
                cout << "NOT UNIQUE";
                return;
            }
        }
    }
    if (la == -1) {
        cout << "NOT POSSIBLE";
        return;
    }
    cout << s.substr(la, ra - la + 1);
}

int32_t main() {
    clock_t startTime = clock();
    cin.tie(0)->sync_with_stdio(false);
    srand(time(0));

    std::istream &in(std::cin);
    std::ostream &out(std::cout);

    int32_t queries = 1;

#ifdef test_cases
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    cin >> queries;
#else
    // cin >> queries;
#endif

    for (int32_t test_case = 1; test_case <= queries; test_case++) {
        print(test_case);
        solution(cin, cout, test_case);
        cout << nl;
    }

#ifdef sunnatov
    cout << "Time: " << (int) ((double) (clock() - startTime) / CLOCKS_PER_SEC * 1000) << " ms" << endl;
#endif

    return EXIT_SUCCESS;
}

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