Submission #794632

#	Time	Username	Problem	Language	Result	Execution time	Memory
794632		bane	Three Friends (BOI14_friends)	C++17	100 / 100	101 ms	39480 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;
     
    const int m = (int)1e9 + 9;
	const int p = 9973;

	ll bpow(ll a, ll b){
		ll res = 1;
		while(b){
			if (b & 1)res = (res * a)%m;
			b /= 2;
			a = (a * a)%m;
		}
		return res;
	}

    void solve(){
		int n;
		string s;
    	cin >> n >> s;
    	if (n % 2 == 0){
    		cout << "NOT POSSIBLE" << endl;
    		return;
    	}
    	
    	ll hsh[n+1];
		hsh[0] = 0;
		for (int i = 0; i < n; i++){
			hsh[i + 1] = (hsh[i] * p % m + (s[i] - 'A' + 1))%m;
		//	cout << hsh[i + 1] << endl;
		}
		ll ps[n + 1];
		ps[0] = 1;
		for (int i = 1; i <= n; i++){
			ps[i] = p * ps[i - 1];
			ps[i] %= m;
		}
		function<ll(int,int)>get = [&](int a, int b){
			return (hsh[b + 1] - hsh[a] * ps[b - a + 1]%m + m)%m;
		};
		unordered_set<ll>se;
		string res = "";
		for (int i = 0; i < n; i++){
			ll hash1 = 0, hash2 = 0;
			if (i == 0){
				hash1 = get(1,n / 2);
				hash2 = get(n/2+1,n - 1);
			}
			else if (i == n / 2){
				hash1 = get(0,i-1);
				hash2 = get(i+1,n - 1);
			}else if (i < n / 2){
				hash1 = (get(0, i - 1) * ps[n / 2 - i] + get(i + 1, n / 2))%m;
				hash2 = get(n - n / 2, n - 1);
			}else{
				hash1 = get(0, n / 2 - 1);
				hash2 = get(n / 2, i - 1) * ps[n / 2 - (i - 1 - (n / 2) + 1)] % m + get(i + 1, n - 1);
			}
			hash1 %= m;
			hash2 %= m;
			debug(hash1,hash2);
			if (hash1 == hash2){
				if (se.empty()){
					for (int j = 0; j < n; j++){
						if (i == j)continue;
						if ((int)res.size() < n / 2)res += s[j];
						else break;
					}
				}
				se.insert(hash1);
				if (se.size() > 1){
					cout << "NOT UNIQUE" << endl;
					return;
				}
			}
		}
		if (res.size() == 0)cout << "NOT POSSIBLE" << endl;
		else cout << res << endl;
    }
     
    int main(){
    	ios::sync_with_stdio(0);
    	cin.tie(0);	
		cout.tie(0);
    	int tt = 1;
    	//cin >> tt;
    	while(tt--){
    		solve();
    	}
    	return 0;
    }

Compilation message (stderr)

friends.cpp: In function 'void solve()':
friends.cpp:15:24: warning: statement has no effect [-Wunused-value]
   15 |     #define debug(...) 42
      |                        ^~
friends.cpp:104:4: note: in expansion of macro 'debug'
  104 |    debug(hash1,hash2);
      |    ^~~~~

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