Submission #533865

#	Time	Username	Problem	Language	Result	Execution time	Memory
533865		groshi	Three Friends (BOI14_friends)	C++17	100 / 100	39 ms	38492 KiB

friends

#include<iostream>
#define ll long long
using namespace std;
long long potegi[3000000];
long long hasze_tyl[3000000];
//long long pierwsza=10;
long long pierwsza=368345561;
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int n;
    cin>>n;
    string s;
    cin>>s;
    potegi[0]=1;
    for(int i=1;i<=n;i++)
        potegi[i]=potegi[i-1]*pierwsza;
    for(int i=n-1;i>=0;i--)
        hasze_tyl[i]=hasze_tyl[i+1]*pierwsza+(s[i]-'A'+1);
    int wyn=-1;
    ll mam;
    for(int i=0;i<n;i++)
    {
        ll pocz,dokon,kon;
        if(i<n/2)
        {
            pocz=hasze_tyl[0]-hasze_tyl[i]*potegi[i];
            dokon=hasze_tyl[i+1]-potegi[n/2-i]*hasze_tyl[n/2+1];
            dokon*=potegi[i];
            pocz+=dokon;
            kon=hasze_tyl[n/2+1];
        }
        else if(i==n/2)
        {
            pocz=hasze_tyl[0]-hasze_tyl[i]*potegi[i];
            kon=hasze_tyl[n/2+1];
        }
        else{
            pocz=hasze_tyl[0]-hasze_tyl[n/2]*potegi[n/2];
            kon=hasze_tyl[n/2]-hasze_tyl[i]*potegi[i-n/2];
            dokon=hasze_tyl[i+1];
            dokon*=potegi[i-n/2];
            kon+=dokon;
        }
        if(pocz!=kon)
            continue;
        if(wyn==-1)
        {
            wyn=i;
            mam=pocz;
        }
        else if(mam!=pocz)
        {
            wyn=-2;
            break;
        }
    }
    if(wyn==-1)
        cout<<"NOT POSSIBLE";
    else if(wyn==-2)
        cout<<"NOT UNIQUE";
    else{
        string jeden="";
        for(int i=0;i<n;i++)
        {
            if(i==wyn)
                continue;
            if(jeden.size()<n/2)
                jeden+=s[i];
        }
        cout<<jeden;
    }
    return 0;
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:70:28: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |             if(jeden.size()<n/2)
      |                ~~~~~~~~~~~~^~~~

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