| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 41348 | gabrielsimoes | 세 명의 친구들 (BOI14_friends) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const string not_possible = "NOT POSSIBLE";
const string not_unique = "NOT UNIQUE";
const ll MOD = 1645333507;
const ll BASE = 137;
ll buildHash(int i, int len, string s) {
ll result = 0;
while (len--) result = (result * BASE + ll(s[i] - 'A')) % MOD;
return result;
}
bool test(string a, string b) {
vector<bool> pref(b.size(), false), suf(b.size(), false);
for (int i = 0; i < a.size(); i++) {
if (a[i] == b[i])
pref[i] = true;
else
break;
}
for (int i = a.size() - 1; i >= 0; i--) {
if (a[i] == b[i + 1])
suf[u + 1] = true;
else
break;
}
for (int i = 0; i < b.size(); i++)
if ((i == 0 || pref[i - 1]) && (i == (b.size() - 1) || suf[i + 1]))
return true;
return false;
}
int main() {
int n, m;
string s;
cin >> n >> s;
m = n / 2;
if (n < 3 || n != m * 2 + 1) {
cout << not_possible << endl;
return 0;
}
bool equalParts = 1;
for (int i = 0; i < m; i++)
if (s[i] != s[m + 1 + i]) equalParts = false;
if (equalParts) {
cout << s.substr(0, m) << endl;
return 0;
}
bool ansl = test(s.substr(0, m), s.substr(m, m + 1));
bool ansr = test(s.substr(m + 1, m), s.substr(0, m + 1));
if (ansl && ansr)
cout << not_unique << endl;
else if (ansl)
cout << s.substr(0, m) << endl;
else if (ansr)
cout << s.substr(m + 1, m) << endl;
else
cout << not_possible << endl;
}