Submission #931166

#	Time	Username	Problem	Language	Result	Execution time	Memory
931166		Bzslayed	Three Friends (BOI14_friends)	C++17	0 / 100	17 ms	5120 KiB

friends

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds; 

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define pff pair<float, float>
#define coutpair(p) cout << p.first << " " << p.second << "\n"

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;

int main(){
    ios_base::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0);

    int n; cin >> n;
    string s; cin >> s;
    unordered_map<char, int> m;

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

    int cnt = 0, occur = 0;
    char nl = '2';
    string ans;
    bool allsame = true;

    for (int i=0; i<s.length(); i++){
        m[s[i]]++;
        if (i > 0 && s[i] != s[i-1]) allsame = false;
    }

    if (allsame){
        for (int i=0; i<n/2; i++) cout << s[i];
        return 0;
    }
    for (auto it : m){
        if (it.second%2!=0 && it.second != nl){
            cnt++;
            nl = it.first;
            occur = m[it.first];
        }

        if (cnt > 1){
            cout << "NOT POSSIBLE";
            return 0;
        }
    }

    for (int i=0; i<s.length(); i++){
        if (s[i] == nl && m[s[i]] == occur/2+1) continue;
        else if (s[i] == nl && m[s[i]] > occur/2+1) m[s[i]]--;
        ans += s[i];

        if (ans.length() == s.length()/2) break;
    }

    m[nl] = 0;
    string ans2;

    for (int i=n-1; i>=0; i--){
        if (s[i] == nl) m[s[i]]++;
        ans2 += s[i];
        if (m[s[nl]] > occur/2 || ans2.length() == s.length()/2) break;
    }

    reverse(ans2.begin(), ans2.end());
    //cout << ans << " " << ans2 << " " << nl << " " << occur << "\n";

    if (s[0] == nl && s[s.length()-1] == nl) cout << "NOT UNIQUE";
    else if (ans == ans2) cout << ans;
    else cout << "NOT POSSIBLE";

    return 0;
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i=0; i<s.length(); i++){
      |                   ~^~~~~~~~~~~
friends.cpp:61:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for (int i=0; i<s.length(); i++){
      |                   ~^~~~~~~~~~~

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