Submission #1079064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079064		steveonalex	Three Friends (BOI14_friends)	C++17	100 / 100	134 ms	97100 KiB

friends

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
#define block_of_code if(true)
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll gcd(ll a, ll b){return __gcd(a, b);}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}
 
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
 
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
double rngesus_d(double l, double r){
    double cur = rngesus(0, MASK(60) - 1);
    cur /= MASK(60) - 1;
    return l + cur * (r - l);
}
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }
 
template <class T>
    void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
        for(auto item: container) out << item << separator;
        out << finish;
    }
 
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

const long N = 2e6 + 69;
const long MOD1 = 1e9 + 7, MOD2 = 1e9 + 9;
const long BASE = 307;
 
ll pow1[N], pow2[N];
void prepare(){
    pow1[0] = pow2[0] = 1;
    for(long i = 1; i<N; ++i){
        pow1[i] = pow1[i-1] * BASE % MOD1;
        pow2[i] = pow2[i-1] * BASE % MOD2;
    }
}
 
struct Hash{
    long n;
    vector<ll> hash1, hash2;
 
    Hash(){}
 
    Hash(string s){
        n = s.size();
        hash1.resize(n+1), hash2.resize(n+1);
        for(long i = 1; i<=n; ++i){
            hash1[i] = (hash1[i-1] + s[i-1] * pow1[i-1]) % MOD1;
            hash2[i] = (hash2[i-1] + s[i-1] * pow2[i-1]) % MOD2;
        }
    }
 
    ll get1(long l, long r){
        return (hash1[r] - hash1[l - 1] + MOD1) * pow1[N - l] % MOD1;
    }
    ll get2(long l, long r){
        return (hash2[r] - hash2[l - 1] + MOD2) * pow2[N - l] % MOD2;
    }
    ll getCode(long l, long r){return get1(l, r) * MOD2 + get2(l, r);}
};

ll join(ll first_half, ll second_half, int l){
    ll hash1 = first_half / MOD2, hash2 = first_half % MOD2;
    ll hash3 = second_half / MOD2, hash4 = second_half % MOD2;
    hash1 = (hash1 + hash3 * pow1[l]) % MOD1;
    hash2 = (hash2 + hash4 * pow2[l]) % MOD2;
    return hash1 * MOD2 + hash2;
}

int main(void){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    clock_t start = clock();

    prepare();

    int n; cin >> n;
    string s; cin >> s;

    if (n % 2 == 0){
        cout << "NOT POSSIBLE\n";
        return 0;
    }

    vector<int> pos;
    vector<ll> unique_ness;
    Hash x(s);
    s = "#" + s;
    int mid_point = (n + 1) / 2;
    for(int i = 1; i<=n; ++i){
        if (i < mid_point){
            ll code = x.getCode(mid_point + 1, n);
            ll first_half = x.getCode(1, i - 1), second_half = x.getCode(i + 1, mid_point);
            if (code == join(first_half, second_half, i - 1)) {
                pos.push_back(i);
                unique_ness.push_back(code);
            }
        }
        else if (i == mid_point){
            if (x.getCode(1, mid_point - 1) == x.getCode(mid_point + 1, n)) {
                pos.push_back(i);
                unique_ness.push_back(x.getCode(1, mid_point - 1));
            }
        }
        else{
            ll code = x.getCode(1, mid_point - 1);
            ll first_half = x.getCode(mid_point, i - 1), second_half = x.getCode(i + 1, n);
            if (code == join(first_half, second_half, i - mid_point)) {
                pos.push_back(i);
                unique_ness.push_back(code);
            }
        }
    }

    bool check_unique_ness = true;
    for(int i = 1; i < unique_ness.size(); ++i) if (unique_ness[i] != unique_ness[i-1]) check_unique_ness = false;

    if (pos.empty()) cout << "NOT POSSIBLE\n";
    else if (!check_unique_ness) cout << "NOT UNIQUE\n";
    else{
        int x = pos[0];
        string ans = "";
        for(int i = 1; i<=n; ++i) if (x != i) ans.push_back(s[i]);
        cout << ans.substr(0, n/2) << "\n";
    }


    cerr << "Time elapsed: " << clock() - start << " ms\n";
    return 0;
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:145:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |     for(int i = 1; i < unique_ness.size(); ++i) if (unique_ness[i] != unique_ness[i-1]) check_unique_ness = false;
      |                    ~~^~~~~~~~~~~~~~~~~~~~

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