#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
void solve() {
int n;
cin >> n;
string s;
cin >> s;
if (n % 2 == 0) {
cout << "NOT POSSIBLE";
return;
}
set<int> ans;
set<ar<int,2>> bugs;
for (int i = 0; i < n / 2;i++) {
if (s[i] != s[i + n / 2 + 1]) bugs.insert({i, i + n / 2 + 1});
}
auto bl = bugs;
auto br = bugs;
for (int i = 1; i <= n / 2;i++) {
int l = n / 2 - i;
int r = n / 2 + i;
//cerr << l << " " << l + n / 2 + 1 << " " << n / 2 - i + 1 << "\n";
if (s[l] != s[l + n / 2 + 1]) {
bl.erase({l, l + n / 2 + 1});
}
if (s[n / 2 - i + 1] != s[l + n / 2 + 1]) {
bl.insert({n / 2 - i + 1, s[l + n / 2 + 1]});
}
// cerr << r << " " << r - n / 2 - 1 << " " << n / 2 + i - 1 << "\n";
if (s[r] != s[r - n / 2 - 1]) {
br.erase({ r - n / 2 - 1,r});
}
if (s[n / 2 + i - 1] != s[r - n / 2 - 1]) {
br.insert({r - n / 2 - 1,n / 2 + i - 1 });
}
if (bl.empty()) ans.insert(l);
if (br.empty()) ans.insert(r);
}
if (ans.size() > 1) cout << "NOT UNIQUE";
else if (ans.empty()) cout << "NOT POSSIBLE";
else {
int cnt = 0,ok = 0;
for (int i = 0; cnt < n / 2;i++) {
if (ok == 0 && ans.count(i)) {
ok = 1;
continue;
}
cout << s[i];
cnt++;
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
//cin >> t;
while (t--) {
solve();
cout << "\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |