oj.uz

Submission #38466

# Submission time Handle Problem Language Result Execution time Memory
38466 2018-01-04T09:27:26 Z oTTo_22 Three Friends (BOI14_friends) C++14
0 / 100
 500 ms 15984 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
const int INF=1e9+1;
const int MAXN=1e5+1;
const int MOD=13371337;
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);

    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

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

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

    bool cnt=0;
    string ans;

    for (int i=0; i<n; i++) {
        string st=s;
        st.erase(i,1);
        vector < int > p=pfunc(st);
        //for (int i=0; i<n-1; i++)
        //    cout << p[i] << " ";
        //cout << "\n";
        if (p[n-2]>=(n-1)/2) {
            if (cnt) {
                cout << "NOT UNIQUE";
                return 0;
            }
            else {
                cnt++;
                for (int j=0; j<(n-1)/2; j++)
                    ans+=st[j];
            }
        }
    }

    if (cnt==0)
        cout << "NOT POSSIBLE";
    else
        cout << ans;

    return 0;
}

Compilation message

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

Subtask #1
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2176 KB Output is correct
2 Correct 0 ms 2176 KB Output is correct
3 Correct 0 ms 2176 KB Output is correct
4 Correct 0 ms 2176 KB Output is correct
5 Correct 0 ms 2176 KB Output is correct
6 Correct 0 ms 2176 KB Output is correct
7 Correct 0 ms 2176 KB Output is correct
8 Correct 0 ms 2176 KB Output is correct
9 Correct 0 ms 2176 KB Output is correct
10 Correct 0 ms 2176 KB Output is correct
11 Correct 0 ms 2176 KB Output is correct
12 Correct 0 ms 2176 KB Output is correct
13 Correct 0 ms 2176 KB Output is correct
14 Correct 0 ms 2176 KB Output is correct
15 Correct 0 ms 2176 KB Output is correct
16 Correct 0 ms 2176 KB Output is correct
17 Correct 0 ms 2176 KB Output is correct
18 Correct 0 ms 2176 KB Output is correct
19 Incorrect 0 ms 2176 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Execution timed out 500 ms 15984 KB Execution timed out
2 Halted 0 ms 0 KB -