이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> z_function(string s) {
int n = s.size();
vector<int> ans(n);
int l = 0, r = 0;
for (int i = 1; i < n; ++i) {
//if (i < r) {
//ans[i] = min(r - i, ans[i - l]);
//}
while (i + ans[i] < n && s[i + ans[i]] == s[ans[i]])
++ans[i];
if (r < i + ans[i]) {
l = i;
r = i + ans[i];
}
}
return ans;
}
signed main() {
int n;
cin >> n;
string s;
cin >> s;
if (n % 2 == 0) {
cout << "NOT POSSIBLE\n";
return 0;
}
vector<int> zs = z_function(s);
reverse(s.begin(), s.end());
vector<int> rzs = z_function(s);
reverse(s.begin(), s.end());
reverse(rzs.begin(), rzs.end());
vector<int> ans;
int m = n / 2;
for (int i = 0; i < m; ++i) {
if (zs[m + 1] >= i && rzs[m] >= m - i)
ans.push_back(i);
}
if (s.substr(0, m) == s.substr(m + 1, m))
ans.push_back(m);
for (int i = m + 1; i < n; ++i) {
if (zs[m] >= i - m && rzs[m - 1] >= n - i - 1)
ans.push_back(i);
}
if (ans.empty()) {
cout << "NOT POSSIBLE\n";
return 0;
}
if ((ans[0] < m) != (ans.back() < m) && s.substr(0, m) != s.substr(m + 1, m)) {
cout << "NOT UNIQUE\n";
return 0;
}
s.erase(s.begin() + ans[0]);
cout << s.substr(0, n / 2);
}
컴파일 시 표준 에러 (stderr) 메시지
friends.cpp: In function 'std::vector<int> z_function(std::string)':
friends.cpp:10:9: warning: variable 'l' set but not used [-Wunused-but-set-variable]
10 | int l = 0, r = 0;
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |