Submission #648346

#	Time	Username	Problem	Language	Result	Execution time	Memory
648346		Ronin13	Three Friends (BOI14_friends)	C++14	0 / 100	315 ms	71156 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 = 998244353;
ll p[NMAX][2];
ll h[NMAX][2];
ll pr[] = {31, 29};

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

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

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


    int ans = -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 = true;
        for(int i = 0; i < 2 ;i++){
            bool ind1 = false;
        if(j < n / 2){
            ll x = 0, y = 0;
            if(j)
                x = get(0, j - 1, i);
            y = get(j + 1, n / 2, i);
            x *= p[n / 2 - j][i]; x %= mod;
            x += y;
            x %= mod;
            ll z = get(n / 2 + 1, n - 1, i);
            if(x == z) ind1= true;
        }
        if(j == n / 2){
            ll x = get(0, n / 2 - 1, i);
            ll z = get(n / 2 + 1, n - 1, i);
            if(x == z) ind1 = true;
        }
        if(j > n / 2){
            ll x = get(n / 2, j - 1, i);
            ll y = 0;
            if(j < n - 1) y = get(j + 1, n - 1, i);
            x *= p[n - j - 1][i];
            x %= mod; x += y;
            x %= mod;
            ll z = get(0, n / 2 - 1, i);
            if(x == z) ind1 = true;
        }
        ind &= ind1;

    }
    if(ind){
        if(ans != -1){
            cout << j << ' ';
            cout << "NOT UNIQUE";
            return 0;
        }
        ans = j;
    }
    }
    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&, int)':
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:107:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for(int i = 0; i < res.size() / 2; i++){
      |                    ~~^~~~~~~~~~~~~~~~
friends.cpp:55:9: warning: unused variable 'len' [-Wunused-variable]
   55 |     int len = n / 2;
      |         ^~~

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