Submission #648361

#	Time	Username	Problem	Language	Result	Execution time	Memory
648361		Ronin13	Three Friends (BOI14_friends)	C++14	100 / 100	148 ms	40688 KiB

friends

#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;

const int NMAX = 2e6 + 1;
const ll mod = 1e9 + 7;
ll p[NMAX];
ll h[NMAX];
const ll pr = 31;

void hashing(string &s){
    h[0] = s[0] - 'A' + 1;
    for(int i = 1; i < s.size(); i++){
        int x = s[i] - 'A' + 1;
        h[i] = h[i - 1] * pr + (ll)x;
        h[i] %= mod;
    }
}

ll get(int l, int r){
    if(l == 0) return h[r];
    ll x = h[r];
    ll y = h[l - 1]; y *= p[r - l + 1]; y %= mod;
    x -= y; x %= mod; x += mod; x %= mod;
    return x % mod;
}

int main(){
    int n; cin >> n;
    for(int i = 0; i < n; i++){
        if(i)
            p[i] = p[i - 1] * pr % mod;
        else p[i] = 1;
        //cout << p[i] << ' ';
    }
    string s; cin >> s;
    hashing(s);


    int ans = -1;
    int anshash = -1;
    if(n % 2 == 0){
        cout << "NOT POSSIBLE";
        return 0;
    }
   // cout << get(4, 6);
    int len = n / 2;
    for(int j = 0; j < n; j++){
        bool ind = false;
        ll curhash = 0;
        if(j < n / 2){
            ll x = 0, y = 0;
            if(j)
                x = get(0, j - 1);
            y = get(j + 1, n / 2);
            x *= p[n / 2 - j]; x %= mod;
            x += y;
            x %= mod;
            ll z = get(n / 2 + 1, n - 1);
            if(x == z) ind = true, curhash = z;
        }
        if(j == n / 2){
            ll x = get(0, n / 2 - 1);
            ll z = get(n / 2 + 1, n - 1);
            if(x == z) ind = true, curhash = z;
        }
        if(j > n / 2){
            ll x = get(n / 2, j - 1);
            ll y = 0;
            if(j < n - 1) y = get(j + 1, n - 1);
            x *= p[n - j - 1];
            x %= mod; x += y;
            x %= mod;
            ll z = get(0, n / 2 - 1);
            if(x == z) ind = true, curhash = z;
        }
        if(ind){
            if(ans != -1 && anshash != curhash){
                cout << "NOT UNIQUE";
                return 0;
            }
            ans = j;
            anshash = curhash;
        }
    }
    if(ans == -1){
        cout << "NOT POSSIBLE";
        return 0;
    }
    string res = "";
    for(int i = 0; i < n; i++){
        if(i == ans) continue;
        res += s[i];
    }
    for(int i = 0; i < res.size() / 2; i++){
        cout << res[i];
    }
    return 0;
}

Compilation message (stderr)

friends.cpp: In function 'void hashing(std::string&)':
friends.cpp:20:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i = 1; i < s.size(); i++){
      |                    ~~^~~~~~~~~~
friends.cpp: In function 'int main()':
friends.cpp:102:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int i = 0; i < res.size() / 2; i++){
      |                    ~~^~~~~~~~~~~~~~~~
friends.cpp:54:9: warning: unused variable 'len' [-Wunused-variable]
   54 |     int len = n / 2;
      |         ^~~

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