Submission #477331

#	Time	Username	Problem	Language	Result	Execution time	Memory
477331		Lobo	Three Friends (BOI14_friends)	C++17	100 / 100	46 ms	11032 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 ans1, ans2;

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

    for(ii i = mid; i < n; i++) {
        s2.pb(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(ans1.size() == 0) ans1 = s1;
        }

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

    //segunda parte

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

    for(ii i = mid+1; i < n; i++) {
        s1.pb(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(ans2.size() == 0) ans2 = s1;
        }

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

    if(ans1 == ans2) {
        ans2 = "";
    }

    if(ans1.size() < ans2.size()) swap(ans1,ans2);

    if(ans1.size() == 0) 
        cout << "NOT POSSIBLE" << endl;
    else if(ans2.size() == 0)
        cout << ans1 << endl;
    else {
        cout << "NOT UNIQUE" << endl;
    }

    return 0;

}

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