Submission #1167908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167908		edgar888mik	Three Friends (BOI14_friends)	C++20	0 / 100	765 ms	327680 KiB

friends

#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <string>
#include <stdio.h>
#include <fstream>
#include <climits>
#include <algorithm>
using namespace std;

class SegmentTree {
    vector<int> tree;
    int n;

    void buildT(vector<int>& arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        }
        else {
            int mid = (start + end) / 2;
            buildT(arr, 2 * node + 1, start, mid);
            buildT(arr, 2 * node + 2, mid + 1, end);
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }
    }

    void updateT(int node, int start, int end, int idx, int value) {
        if (start == end) {
            tree[node] = value;
        }
        else {
            int mid = (start + end) / 2;
            if (idx <= mid)
                updateT(2 * node + 1, start, mid, idx, value);
            else
                updateT(2 * node + 2, mid + 1, end, idx, value);
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }
    }

    int queryT(int node, int start, int end, int l, int r) {
        if (r < start || end < l)
            return 0;
        if (l <= start && end <= r)
            return tree[node];
        int mid = (start + end) / 2;
        int leftQuery = queryT(2 * node + 1, start, mid, l, r);
        int rightQuery = queryT(2 * node + 2, mid + 1, end, l, r);
        return leftQuery + rightQuery;
    }

    void build(vector<int>& arr) {
        n = arr.size();
        tree = vector<int>(4 * n, 0);
        buildT(arr, 0, 0, n - 1);
    }

    void update(int idx, int value) {
        updateT(0, 0, n - 1, idx, value);
    }

    int query(int l, int r) {
        return queryT(0, 0, n - 1, l, r);
    }
};

long long int prime = 83, mod = 1e9 + 7;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    /*freopen("paintbarn.in", "r", stdin);
    freopen("paintbarn.out", "w", stdout);*/

    int n;
    int answer = 0;
    string ans = "";
    string str;
    cin >> str;
    n = str.size();
    if (n % 2 == 1)
    {
        int ln = (n - 1) / 2;
        string possibleAns = "";
        int possible = 0;
        possible = 1;
        for (int i = 1; i <= ln; i++)
        {
            if (str[i] == str[i + ln])
            {
                possibleAns += str[i];
            }
            else
            {
                possible = 0;
                possibleAns = "";
                break;
            }
        }
        if (possible)
        {
            ans = possibleAns;
            answer++;
        }
        possibleAns = "";
        possible = 0;

        possible = 1;
        for (int i = str.size() - 2; i >= str.size() - 1 - ln ; i--)
        {
            if (str[i] == str[i - ln])
            {
                possibleAns += str[i];
            }
            else
            {
                possible = 0;
                possibleAns = "";
                break;
            }
        }

        if (possible)
        {
            reverse(possibleAns.begin(), possibleAns.end());
            ans = possibleAns;
            answer++;
        }
        possibleAns = "";
        possible = 0;

        string TheStart = "", TheEnd = "", saveEnd, saveStart;
        long long int hashS = 0, hashE = 0, hashAll = 0;
        for (int i = 0; i < ln; i++)
        {
            TheStart += str[i];
        }
        saveStart = TheStart;
        TheStart = TheStart + TheStart;
        for (int i = str.size() - ln; i <= str.size() - 1; i++)
        {
            TheEnd += str[i];
        }
        saveEnd = TheEnd;
        TheEnd = TheEnd + TheEnd;
        int d = 0;

        vector <long long> prefS, prefE, pref, sufS(str.size() - 1), sufE(str.size() - 1), suf(str.size());
        for (int i = 0; i < TheStart.size(); i++)
        {
            hashS = (hashS * prime + TheStart[i] - 'A') % mod;
            hashE = (hashE * prime + TheEnd[i] - 'A') % mod;
            prefS.push_back(hashS);
            prefE.push_back(hashE);
        }
        for (int i = 0; i < str.size(); i++)
        {
            hashAll = (hashAll * prime + str[i] - 'A') % mod;
            pref.push_back(hashAll);
        }
        hashS = 0;
        hashE = 0;
        hashAll = 0;

        for (int i = TheStart.size() - 1; i >= 0; i--)
        {
            hashS = (hashS * prime + TheStart[i] - 'A') % mod;
            hashE = (hashE * prime + TheEnd[i] - 'A') % mod;
            sufS[i] = hashS;
            sufE[i] = hashE;
        }
        for (int i = str.size() - 1; i >= 0; i--)
        {
            hashAll = (hashAll * prime + str[i] - 'A') % mod;
            suf[i]  = hashAll;
        }
        hashS = 0;
        hashE = 0;
        hashAll = 0;

        for (int i = 1; i < str.size() - 1; i++)
        {
            long long int lHash = 0, rHash = 0;
            lHash = pref[i - 1];
            rHash = suf[i + 1];
            if (i < ln)
            {
                long long int calculatedLeftHash, calculatedRightHash;
                calculatedLeftHash = prefE[i - 1];
                calculatedRightHash = sufE[i];
                if (calculatedLeftHash == lHash && calculatedRightHash == rHash)
                {
                    answer++;
                    ans = saveEnd;
                }
            }
            else
            {
                long long int calculatedLeftHash, calculatedRightHash;
                calculatedLeftHash = prefS[i - 1];
                calculatedRightHash = sufS[i];
                if (calculatedLeftHash == lHash && calculatedRightHash == rHash)
                {
                    answer++;
                    ans = saveStart;
                }
            }
        }
    }
    if (answer == 0)
    {
        cout << "NOT POSSIBLE" << endl;
    }
    else if (answer > 1)
    {
        cout << "NOT UNIQUE" << endl;
    }
    else
    {
        cout << ans << endl;
    }
}

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