Submission #860787

#TimeUsernameProblemLanguageResultExecution timeMemory
860787EllinorThree Friends (BOI14_friends)C++14
100 / 100
17 ms6164 KiB
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
#pragma GCC optimize ("unroll-loops")

#pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      // bit manipulation
#pragma GCC target("movbe")                                      // byte swap
#pragma GCC target("aes,pclmul,rdrnd")                           // encryption
#pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2")

typedef long long ll;
#define rep(i, a, b) for (int i = (a); i < int(b); i++)
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define pb push_back

inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }

ll INF = 1000000000;
ll mod = 1e9 + 7;

#define int ll
#define float double

//
ll N;
string s;

int32_t main()
{
    fast();
    cin >> N;
    cin >> s;
    if (N % 2 == 0) {
        cout << "NOT POSSIBLE\n";
        exit(0);
    }

    ll n = N / 2;
    vector<string> ans;

    if (s[1] == s[n + 1]) {
        string ns = "";
        ns.pb(s[1]);
        rep(at, 2, n + 1) {
            if (s[at] == s[n + at]) {
                ns.pb(s[at]);
            }
            else break;
        }
        if (ns.size() == n) {
            ans.pb(ns);
        }
    }

    if (s[0] == s[n]) {
        int p = 0;
        string ns = "";
        ns.pb(s[0]);
        rep(at, 1, n) {
            if (s[at] == s[n + at + p]) {
                ns.pb(s[at]);
            }
            else if (p == 0) {
                p = 1;
                at--;
            }
            else break;
        }
        if (ns.size() == n) {
            if (ans.size() == 1) {
                bool same = true;
                rep(i,0,n) {
                    if (ns[i] != ans[0][i]) {
                        same = false;
                        break;
                    }
                }
                if (!same) ans.pb(ns);
            }
            else ans.pb(ns);
        }
    }

    if (s[0] == s[n+1]) {
        int p = 0;
        string ns = "";
        ns.pb(s[n+1]);
        rep(at, 1, n) {
            if (s[at + p] == s[n + 1 + at]) {
                ns.pb(s[n + 1 + at]);
            }
            else if (p == 0) {
                p = 1;
                at--;
            }
            else break;
        }
        if (ns.size() == n) {
            if (ans.size() > 0) {
                bool bb = false;
                rep(j, 0, ans.size()) {
                    bool same = true;
                    rep(i,0,n) {
                        if (ns[i] != ans[j][i]) {
                            same = false;
                            break;
                        }
                    }
                    if (same) bb = true;
                }
                if (!bb) ans.pb(ns);
            }
            else ans.pb(ns);
        }
    }
    
    if (ans.size() == 1) cout << ans[0] << "\n";
    else if (ans.size() > 1) cout << "NOT UNIQUE\n";
    else cout << "NOT POSSIBLE\n";
}

Compilation message (stderr)

friends.cpp: In function 'int32_t main()':
friends.cpp:52:23: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   52 |         if (ns.size() == n) {
      |             ~~~~~~~~~~^~~~
friends.cpp:71:23: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   71 |         if (ns.size() == n) {
      |             ~~~~~~~~~~^~~~
friends.cpp:100:23: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  100 |         if (ns.size() == n) {
      |             ~~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...