제출 #477321

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
477321		Lobo	Three Friends (BOI14_friends)	C++17	35 / 100	26 ms	12404 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 220000

ii n, pf[maxn], 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;

    set<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;

    for(ii i = 0; i < mid; i++) {
        if(s1[i] == s2[i]) {
            pf[i] = 1;
        }
        else {
            pf[i] = 0;
        }

        if(i != 0) pf[i] = min(pf[i],pf[i-1]);
    }

    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]);
    }

    if(sf[0] == 1) {
        ans.insert(s1);
    }

    for(ii i = 0; i < mid; i++) {
        //cout << i << " pf " << pf[i] << endl;
        //cout << i+1 << " sf " << sf[i+1] << endl;
        //cout << endl;
        if(pf[i] == 1 && sf[i+1] == 1) {
            ans.insert(s1);
        }
    }

    //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;

    for(ii i = 0; i < mid; i++) {
        if(s1[i] == s2[i]) {
            pf[i] = 1;
        }
        else {
            pf[i] = 0;
        }

        if(i != 0) pf[i] = min(pf[i],pf[i-1]);
    }

    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]);
    }

    if(sf[0] == 1) {
        ans.insert(s1);
    }

    for(ii i = 0; i < mid; i++) {
        //cout << i << " pf " << pf[i] << endl;
        //cout << i+1 << " sf " << sf[i+1] << endl;
        //cout << endl;
        if(pf[i] == 1 && sf[i+1] == 1) {
            ans.insert(s1);
        }
    }


    if(ans.size() == 0) {
        cout << "NOT POSSIBLE" << endl;
    }
    else if(ans.size() == 1) {
        cout << *ans.begin() << endl;
    }
    else {
        cout << "NOT UNIQUE" << endl;
    }

    return 0;

}

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