Submission #38530

#	Time	Username	Problem	Language	Result	Execution time	Memory
38530		oTTo_22	세 명의 친구들 (BOI14_friends)	C++14	0 / 100	26 ms	23632 KiB

friends

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std;

vector < int > pfunc(string str){
    vector < int > p(str.size());
    int j=0;

    for (int i=1; i<str.size(); i++) {
        while (j>0 && str[j]!=str[i])
            j=p[j-1];

        if (str[j]==str[i])
            j++;
        p[i]=j;
    }
    return p;
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    string s;
    cin >> n >> s;

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

    bool cnt=0;
    string ss;
    string ans;
    for (int i=n-1; i>=0; i--)
        ss+=s[i];
    if (ss==s) {
        string st=s;
        st.erase(0,1);
        string st1,st2;
        for (int i=0; i<n/2; i++)
            st1+=st[i];
        for (int i=n/2; i<n-1; i++)
            st2+=st[i];
        if (st1==st2) {
            ans=st1;
            cnt++;
        }
        string st3,st4;
        for (int i=0; i<n/2; i++)
            st3+=s[i];
        for (int i=n/2; i<n-1; i++)
            st4+=s[i];
        if (st3==st4) {
            if (ans!=st3) {
                cout << "NOT UNIQUE";
                return 0;
            }
            else {
                cout << ans;
                return 0;
            }
        }
    }

    vector < int > p=pfunc(s);

    int mx=0;
    for (int i=0; i<p.size(); i++)
        mx=max(mx,p[i]);

    string st=s;
    st.erase(0+mx,1);

    string st1,st2;
    for (int i=0; i<n/2; i++)
        st1+=st[i];
    for (int i=n/2; i<n-1; i++)
        st2+=st[i];

    if (st1==st2) {
        cout << st1;
        return 0;
    }

    st=s;
    st.erase(n-1-mx,1);

    string st3,st4;
    for (int i=0; i<n/2; i++)
        st3+=st[i];
    for (int i=n/2; i<n-1; i++)
        st4+=st[i];

    if (st3==st4) {
        cout << st3;
        return 0;
    }

    cout << "NOT POSSIBLE";

    return 0;
}

Compilation message (stderr)

friends.cpp: In function 'std::vector<int> pfunc(std::__cxx11::string)':
friends.cpp:11:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=1; i<str.size(); i++) {
                    ^
friends.cpp: In function 'int main()':
friends.cpp:73:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<p.size(); i++)
                    ^

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