Submission #493989

#	Time	Username	Problem	Language	Result	Execution time	Memory
493989		goodluck2020	Three Friends (BOI14_friends)	C++14	100 / 100	53 ms	13632 KiB

friends

#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";
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen(task ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
friends.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         freopen(task ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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