# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
493989 | goodluck2020 | 세 명의 친구들 (BOI14_friends) | C++14 | 53 ms | 13632 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define task "friends"
using namespace std;
const int N = 1e6 + 10;
int c, n, m, A[N], B[N], ans, res, tmp;
bool L[N], R[N];
string S;
bool CheckMid()
{
for(int i = 0; i < c/2; i++)
if(S[i] != S[i + c/2 + 1]) return 0;
return 1;
}
int CALC()
{
L[0] = 1; R[n + 1] = 1;
for(int i = 1; i <= n; i++)
L[i] = min(L[i-1], (A[i] == B[i]));
for(int i = n; i >= 1; i--)
R[i] = min(R[i+1], (A[i] == B[i - 1]));
for(int i = 1; i <= n; i++)
if(L[i-1] && R[i+1] && (tmp || i != n))
{
res = tmp + i;
return 1;
}
return 0;
}
void TruyVet(int k)
{
if(k > c/2)
for(int i = 0; i < c/2; i++) cout << S[i];
else
for(int i = c/2 + 1; i < c; i++) cout << S[i];
}
int main()
{
if(fopen(task ".inp","r"))
{
freopen(task ".inp","r",stdin);
freopen(task ".out","w",stdout);
}
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> c >> S;
if(c % 2 == 0)
{
cout << "NOT POSSIBLE";
return 0;
}
if(CheckMid())
{
for(int i = 0; i < c/2; i++) cout << S[i];
return 0;
}
for(int i = 0; i <= c/2; i++) A[++n] = S[i] - 'A';
for(int i = c/2 + 1; i < c; i++) B[++m] = S[i] - 'A';
ans += CALC();
n = m = 0;
for(int i = 0; i < c/2; i++) B[++m] = S[i] - 'A';
for(int i = c/2; i < c; i++) A[++n] = S[i] - 'A';
tmp = c/2;
ans += CALC();
if(ans == 1) TruyVet(res);
else if(ans > 1) cout << "NOT UNIQUE";
else cout << "NOT POSSIBLE";
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |