Submission #968750

#	Time	Username	Problem	Language	Result	Execution time	Memory
968750		youssef_3breheem	Three Friends (BOI14_friends)	C++17	0 / 100	68 ms	35584 KiB

friends

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>

using namespace std;

typedef long long ll;
typedef string str;
typedef vector<ll> vint;

const ll MOD1 = 1999998893;
const ll MOD2 = 2100003611;
const ll BASE = 29;
const char STARTING_LETTER = 'A';

ll hashChar(char c) {
    return c - STARTING_LETTER + 1;
}

pair<ll, ll> hashStr(pair<ll, ll> prevHash, char curChar) {
    return {((prevHash.first * BASE) % MOD1 + hashChar(curChar)) % MOD1,
            ((prevHash.second * BASE) % MOD2 + hashChar(curChar)) % MOD2};
}

class RollingHash {
private:
    ll mod1, mod2, base;
    vector<ll> powOfBase1, powOfBase2;

public:
    RollingHash(ll mod1, ll mod2, ll base) : mod1(mod1), mod2(mod2), base(base) {}

    void calculatePowers(int n) {
        powOfBase1.resize(n);
        powOfBase2.resize(n);
        powOfBase1[0] = 1;
        powOfBase2[0] = 1;
        for (int i = 1; i < n; i++) {
            powOfBase1[i] = (base * powOfBase1[i - 1]) % mod1;
            powOfBase2[i] = (base * powOfBase2[i - 1]) % mod2;
        }
    }

    pair<ll, ll> hashString(const str& s) {
        pair<ll, ll> hashValue = {0, 0};
        for (char c : s) {
            hashValue = hashStr(hashValue, c);
        }
        return hashValue;
    }

    pair<ll, ll> updateHash(pair<ll, ll> prevHash, char oldChar, char newChar, int length) {
        pair<ll, ll> newHash = prevHash;
        ll pow1 = powOfBase1[length - 1];
        ll pow2 = powOfBase2[length - 1];
        newHash.first = ((newHash.first - (pow1 * hashChar(oldChar)) % mod1 + mod1) * base + hashChar(newChar)) % mod1;
        newHash.second = ((newHash.second - (pow2 * hashChar(oldChar)) % mod2 + mod2) * base + hashChar(newChar)) % mod2;
        return newHash;
    }
};

str findUniqueString(int n, const str& u) {
    str left = u.substr(0, n / 2 + 1);
    str right = u.substr(n / 2 + 1);

    str ans = "";
    pair<ll, ll> ansHash = {0, 0};

    RollingHash rollingHash(MOD1, MOD2, BASE);
    rollingHash.calculatePowers(n);

    pair<ll, ll> leftHash = rollingHash.hashString(left);
    pair<ll, ll> rightHash = rollingHash.hashString(right);

    for (int i = 0; i < left.size(); i++) {
        pair<ll, ll> newRightHash = rightHash;
        if (i > 0) {
            char oldChar = right[i - 1];
            char newChar = left[i - 1];
            newRightHash = rollingHash.updateHash(rightHash, oldChar, newChar, right.size());
        }

        if (leftHash == newRightHash) {
            for (int j = 0; j < left.size(); j++) {
                if (i != j) ans += left[j];
            }
            ansHash = rollingHash.hashString(ans);
            if (!ans.empty() && ansHash != leftHash) return "NOT UNIQUE";
        }
    }

    if (ans.empty()) return "NOT POSSIBLE";
    return ans;
}

int main() {
    srand(time(0));
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(15);

    int n;
    cin >> n;
    str u;
    cin >> u;

    str result = findUniqueString(n, u);
    cout << result;

    return 0;
}

Compilation message (stderr)

friends.cpp: In function 'str findUniqueString(int, const str&)':
friends.cpp:77:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int i = 0; i < left.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
friends.cpp:86:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |             for (int j = 0; j < left.size(); j++) {
      |                             ~~^~~~~~~~~~~~~

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