Submission #419761

#	Time	Username	Problem	Language	Result	Execution time	Memory
419761		den_tar	Three Friends (BOI14_friends)	C++14	0 / 100	56 ms	4212 KiB

friends

#include <bits/stdc++.h>

using namespace std;

#define fast ios_base::sync_with_stdio();cin.tie();cout.tie();
#define en cout<<endl;
#define ops cout<<"ops"<<endl;
#define line cout<<"---------------------------"<<endl;
#define fi first
#define se second

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pllll;
typedef string str;

const ll DIM = 2e6 + 7;
const ll DIMM = 1e2 + 7;
const ll DDIM = 7;
const ll INF = 1e18 + 7;
const ll X = 1e5 + 7;
const ll BS = 2e5 + 7;
const ll AS = 26 + 7;
const ll MODULO = 1e9 + 7;

ll nt,n,m,k,q;

ll val,val1;

ll c[AS];

ll p1,p2,p3,p4,fl;

vector<ll> r;

str s,s1,res;

int main()
{
    fast;
    //ll x1,y1,x2,y2;

    cin>>n>>s;




    for(int i=0; i<n; i++)
    {
        val=s[i]-'A'+1;
        c[val]++;
    }

    val=(-1);
    for(int i=1; i<=26; i++)
    {
        if(c[i]==1)val=i;
        if(c[i]%2==1)k++;
    }






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

    if(k!=1)
    {
        cout<<"NOT POSSIBLE"<<endl;
        return 0;
    }




    if(val!=(-1))
    {

        ops;

        res="";

        for(int i=0; i<n/2; i++)
        {
            val1=s[i]-'A'+1;
            if(val!=val1)res+=s[i];
        }

        if(res.length() != (n/2))res+=s[n/2];

        cout<<res<<endl;
        return 0;
    }


    fl=0;
    for(int i=1; i<=n/2; i++)
        if(s[i]!=s[i+n/2])
        {
            fl=1;
            break;
        }

    if(fl==0)r.push_back(0);

    fl=0;
    for(int i=0; i<n/2; i++)
        if(s[i]!=s[i+n/2+1])
        {
            fl=1;
            break;
        }

    if(fl==0)r.push_back(n/2);

    p1=0;
    p2=n/2;

    while(s[p1]==s[p2] && p2<(n-2))
    {
        p1++;
        p2++;
    }

    if(p2==(n-2))r.push_back(n-1);
    else
    {
        p3=p1;
        p4=p2;

        if(s[p3+1]==s[p4])
        {
            p3++;

            while(s[p3]==s[p4] && p4<n)
            {
                p3++;
                p4++;
            }

            if(p4==n-1)r.push_back(p1);
        }

        p3=p1;
        p4=p2;

        if(s[p3]==s[p4+1])
        {
            p4++;

            while(s[p3]==s[p4] && p4<n)
            {
                p3++;
                p4++;
            }

            if(p4==n-1)r.push_back(p2);
        }
    }

    if(r.size()==0){
     cout<<"NOT POSSIBLE"<<endl;
     return 0;
    }

    res="";

    for(auto p:r){
     s1="";
     for(int i=0;i<n/2;i++){
      if(i==p)continue;
      s1+=s[i];
     }

     if(s1.length() < n/2)s1+=s[n/2];

     if(res=="")res=s1;
     else if(res!=s1){
      cout<<"NOT UNIQUE"<<endl;
      return 0;
     }

    }

    cout<<res<<endl;

    return 0;
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:94:25: 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]
   94 |         if(res.length() != (n/2))res+=s[n/2];
      |            ~~~~~~~~~~~~~^~~~~~~~
friends.cpp:180:21: 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]
  180 |      if(s1.length() < n/2)s1+=s[n/2];
      |         ~~~~~~~~~~~~^~~~~

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