Submission #945730

#	Time	Username	Problem	Language	Result	Execution time	Memory
945730		phoenix0423	Three Friends (BOI14_friends)	C++17	100 / 100	44 ms	37628 KiB

friends

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
#define lowbit(x) x&-x
const int INF = 1e9 + 7;
const int maxn = 2e6 + 5;
const int A = 923984352;
const int N = 998244353;
int p[maxn];

signed main(void){
	fastio;
	int n;
	cin>>n;
	p[0] = 1;
	for(int i = 1; i < n; i++) p[i] = p[i - 1] * A % N;
	string s;
	cin>>s;
	if(n % 2 == 0){
		cout<<"NOT POSSIBLE\n";
		return 0;
	}
	vector<int> h(n);
	h[0] = s[0];
	for(int i = 1; i < n; i++){
		h[i] = (h[i - 1] * A + s[i]) % N;
	}
	int len = n / 2;
	set<int> match;
	int ans = 0;
	for(int i = 0; i < n; i++){
		if(i <= len){
			int a = ((i ? h[i - 1] * p[len - i] : 0) + h[len] - h[i] * p[len - i] % N + N) % N;
			int b = (h[n - 1] - h[len] * p[len] % N + N) % N;
			if(a == b) match.insert(a), ans = i;
		}
		else{
			int a = h[len - 1];
			int b = ((h[n - 1] - h[i] * p[n - 1 - i] % N + N) + (h[i - 1] - h[len - 1] * p[i - len]) % N * p[n - 1 - i] % N + 2 * N) % N;
			if(a == b) match.insert(a), ans = i;
		}
	}
	if(match.size() >= 2){
		cout<<"NOT UNIQUE\n";
	}
	else if(!match.size()){
		cout<<"NOT POSSIBLE\n";
	}
	else{
		if(ans >= len) cout<<s.substr(0, len);
		else cout<<s.substr(len + 1, len);
		cout<<"\n";
	}
}

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