제출 #477327

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
477327		Lobo	세 명의 친구들 (BOI14_friends)	C++17	35 / 100	1081 ms	10180 KiB

friends

#include <bits/stdc++.h>
 
using namespace std;

const long long INFll = (long long) 1e18 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 2000010

ii n, sf[maxn];
string u, s1, s2;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    //freopen("in.in", "r", stdin);

    cin >> n >> u;

    if(n%2 == 0) {
        cout << "NOT POSSIBLE" << endl;
        return 0;
    }

    ii mid = n/2;
    //cout << u[mid] << endl;

    string ans;

    for(ii i = 0; i < mid; i++) {
        s1+= u[i];
    }

    for(ii i = mid; i < n; i++) {
        s2+= u[i];
    }

    //cout << mid << " " << s1 << " " << s2 << endl;

    sf[mid] = 1;

    for(ii i = mid-1; i >= 0; i--) {
        //cout << s1[i] << " " << s2[i+1] << endl;
        if(s1[i] == s2[i+1]) {
            sf[i] = 1;
        }
        else {
            sf[i] = 0;
        }

        if(i != mid) sf[i] = min(sf[i], sf[i+1]);
    }

    for(ii i = 0; i <= mid; i++) {
        //cout << i << " pf " << pf[i] << endl;
        //cout << i+1 << " sf " << sf[i+1] << endl;
        //cout << endl;
        if(sf[i] == 1) {
            if(ans.size() != 0 && ans != s1) {
                cout << "NOT UNIQUE" << endl;
                return 0;
            }
            else ans = s1;
        }

        if(s1[i] != s2[i]) break;
    }

    //segunda parte

    s1.clear();
    s2.clear();
    for(ii i = 0; i <= mid; i++) {
        s2+= u[i];
    }

    for(ii i = mid+1; i < n; i++) {
        s1+= u[i];
    }

    //cout << mid << " " << s1 << " " << s2 << endl;

    sf[mid] = 1;

    for(ii i = mid-1; i >= 0; i--) {
        //cout << s1[i] << " " << s2[i+1] << endl;
        if(s1[i] == s2[i+1]) {
            sf[i] = 1;
        }
        else {
            sf[i] = 0;
        }

        if(i != mid) sf[i] = min(sf[i], sf[i+1]);
    }

    for(ii i = 0; i <= mid; i++) {
        //cout << i << " pf " << pf[i] << endl;
        //cout << i+1 << " sf " << sf[i+1] << endl;
        //cout << endl;
        if(sf[i] == 1) {
            if(ans.size() != 0 && ans != s1) {
                cout << "NOT UNIQUE" << endl;
                return 0;
            }
            else ans = s1;
        }

        if(s1[i] != s2[i]) break;
    }


    if(ans.size() == 0) 
        cout << "NOT POSSIBLE" << endl;
    else
        cout << ans << endl;

    return 0;

}

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