Submission #794519

#	Time	Username	Problem	Language	Result	Execution time	Memory
794519		bane	Three Friends (BOI14_friends)	C++17	35 / 100	536 ms	83436 KiB

friends

    #include<bits/stdc++.h>
    using namespace std;
     
    /*
    #include <ext/pb_ds/assoc_container.hpp>
    using namespace __gnu_pbds;
    template <class T>
    using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
    */
     
     
    #ifdef LOCAL
    #include "algo/debug.h"
    #else
    #define debug(...) 42
    #endif
     
    #define rep(i, n) for (int i = 0; i < (n); ++i)
    #define rep1(i, n) for (int i = 1; i < (n); ++i)
    #define rep1n(i, n) for (int i = 1; i <= (n); ++i)
    #define repr(i, n) for (int i = (n) - 1; i >= 0; --i)
     
     
    #define fr first
    #define sc second
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(), (x).end()
    #define rall(x) (x).rbegin(), (x).rend()
    #define endl '\n'
     
     
    using ll = long long;
    using ull = unsigned long long;
    using ld = long double;
    using str = string;
    using pi = pair<int, int>;
    using pl = pair<ll, ll>;
     
    using vi = vector<int>;
    using vl = vector<ll>;
    using vpi = vector<pair<int, int>>;
    using vvi = vector<vi>;
     
    const int nax = (int)2000002;
     
    int n, p = 31, m = (int)131071;
    ll hsh[nax];
    string s;
     
    ll bpow(ll u, ll b){
    	ll res = 1;
    	while(b){
    		if (b & 1)res = (res * u)%m;
			b/=2;
			u = (u * u)%m;
    	}
    	return res;
    }
     
    ll inv(ll p){
    	return bpow(p,m-2);
    }
    ll ips[nax + 1];
	ll ps[nax+1];
    void solve(){
    	cin >> n >> s;
    	if (n % 2 == 0){
    		cout << "NOT POSSIBLE" << endl;
    		return;
    	}
    	
    	
    	for (int i = 0; i < n; i++){
    		hsh[i] = (s[i] - 'A' + 1) * ps[i] % m;
    		if (i)hsh[i] += hsh[i - 1];
    		hsh[i]%=m;
    	}
    	//cout << hsh[0] << endl;
    	//cout << ps[3] << endl;
    	int L1[n], R1[n], L2[n], R2[n];
    	unordered_set<ll>se;
    	string res = "";
    	for(int i = 0; i < n; i++){
    		L1[i] = 0;
    		if (i == 0)L1[i]++;
    		R1[i] = L1[i] + n / 2 - 1;
    		if (R1[i] >= i && L1[i] < i)R1[i]++;
    		ll hash1 = 0;
    		if (R1[i] > i && L1[i] < i){
    			hash1 = (i < 1 ? 0 : hsh[i - 1]);
    			hash1 += (((hsh[R1[i]] - hsh[i] + m)%m) * ips[i + 1]%m)
    			* ps[i] % m; 
				hash1 %= m;
    		}else{
    			hash1 = hsh[R1[i]];
    			if (L1[i]){
    				hash1 -= hsh[L1[i] - 1];
    				hash1+=m;
    				hash1 %= m;
    				hash1 *= ips[L1[i]];
    			}
    			hash1 %= m;
    		}
    		L2[i] = R1[i] + 1;
    		if (L2[i] == i)++L2[i];
    		R2[i] = L2[i] + n / 2 - 1;
    		ll hash2 = 0;
    		if (R2[i] >= i && L2[i] < i)++R2[i];
    		//cout << L1[i] << " " << R1[i] << " " << L2[i] << " " << R2[i] << endl;
    		if (L2[i] > i){
    			hash2 = (m + hsh[R2[i]] - hsh[L2[i] - 1])%m;
    			hash2 *= ips[L2[i]];
    			hash2 %= m;
    		}else{
    			hash2 = (hsh[i - 1] - hsh[L2[i] - 1] + m)%m;
    			hash2 *= ips[L2[i]];
    			hash2 %= m;
    			ll hash3 = (m + hsh[R2[i]] - hsh[i])%m;
    			hash3 *= ips[i+1];
    			hash3 %= m;
    			hash3 *= ps[i - L2[i]];
    			hash3 %= m;
    			//if (i == 5)cout << hash3 << endl;
    			if (i - 1 != R2[i]) hash2 += hash3;
				hash2 %= m;
    		}
    		if (hash1 == hash2){
    			if (se.empty()){
    				for (int j = 0; j < n; j++){
    					if (i == j)continue;
    					if (res.size() <  n / 2)res += s[j];
    					else break;
    				}
    			}
    			se.insert(hash1);
    			if (se.size() > 1){
    				cout << "NOT UNIQUE" << endl;
    				return;
    			}
     
    		}
    	}
    	if (se.empty())cout << "NOT POSSIBLE" << endl;
    	else cout << res << endl;
    }
     
    int main(){
    	ios::sync_with_stdio(0);
    	cin.tie(0);	
		cout.tie(0);
    	int tt = 1;
		ps[0] = 1;
    	for (int i = 1; i < nax; i++){
    		ps[i] = p;
    		ps[i] *= ps[i - 1];
    		ps[i] %= m;
    	}
    	for (int i = 0; i < nax; i++){
    		ips[i] = inv(ps[i]);
    	}
    	//cin >> tt;
    	while(tt--){
    		solve();
    	}
    	return 0;
    }

Compilation message (stderr)

friends.cpp: In function 'void solve()':
friends.cpp:132:25: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  132 |          if (res.size() <  n / 2)res += s[j];
      |              ~~~~~~~~~~~^~~~~~~~

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