Submission #732955

#	Time	Username	Problem	Language	Result	Execution time	Memory
732955		n0sk1ll	Three Friends (BOI14_friends)	C++17	100 / 100	387 ms	62984 KiB

friends

#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
//const int mod = 1000000007;







//Note to self: Check for overflow

int power(int a, int n, int mod)
{
    li c=1;
    while (n)
    {
        if (n&1) (c*=a)%=mod;
        a=(li)a*a%mod,n>>=1;
    }
    return c;
}

mt19937 rng(2942023);

char s[2000005];
int w[256];

const int H=2;

struct hesiranje
{
    int pre[2000005];
    int p,mod;
    int pw[2000005];
    int iw[2000005];

    void setprost(int _p)
    {
        p=_p;
    }

    void setmod(int _mod)
    {
        mod=_mod;
    }

    void build(int n)
    {
        ff(i,0,256) w[i]=rng()%mod;

        pw[0]=1;
        fff(i,1,n) pw[i]=(li)pw[i-1]*p%mod;
        iw[0]=1;
        iw[1]=power(p,mod-2,mod);
        fff(i,2,n) iw[i]=(li)iw[i-1]*iw[1]%mod;

        fff(i,1,n) pre[i]=((li)pre[i-1]*p+w[s[i]])%mod;
    }

    int Hash(int ll, int rr)
    {
        return (pre[rr]+mod-(li)pre[ll-1]*pw[rr-ll+1]%mod)%mod;
    }

    int ComboHash(int l1, int r1, int l2, int r2)
    {
        return (Hash(l2,r2)+(li)pw[r2-l2+1]*Hash(l1,r1)%mod)%mod;
    }
} hes[H];

vector<int> brisem; //ako ih ima vise, ispisati not unique; ako ih nema uopste, ispisati not possible

int main()
{
    FAST;

    int n; cin>>n;
    fff(i,1,n) cin>>s[i];
    if (!(n&1)) return cout<<"NOT POSSIBLE",0;

    hes[0].setprost(143);
    hes[0].setmod(998244353);

    hes[1].setprost(1000003);
    hes[1].setmod(998244353);

    /*hes[2].setprost(143);
    hes[2].setmod(1000000007);

    hes[3].setprost(1000003);
    hes[3].setmod(1000000007);

    hes[4].setprost(143);
    hes[4].setmod(1000000009);

    hes[5].setprost(1000003);
    hes[5].setmod(1000000009);*/

    ff(koji,0,H) hes[koji].build(n);

    set<int> hesovi;

    fff(i,1,(n+1)/2)
    {
        bool jednaki=true;
        ff(koji,0,H) if (hes[koji].ComboHash(1,i-1,i+1,(n+1)/2) != hes[koji].Hash((n+1)/2+1,n)) jednaki=false;

        if (jednaki)
        {
            brisem.pb(i);
            hesovi.insert(hes[0].Hash((n+1)/2+1,n));
        }
    }
    fff(i,(n+1)/2+1,n)
    {
        bool jednaki=true;
        ff(koji,0,H) if (hes[koji].Hash(1,(n+1)/2-1) != hes[koji].ComboHash((n+1)/2,i-1,i+1,n)) jednaki=false;

        if (jednaki)
        {
            brisem.pb(i);
            hesovi.insert(hes[0].Hash(1,(n+1)/2-1));
        }
    }

    if (brisem.empty()) return cout<<"NOT POSSIBLE",0;
    if ((int)hesovi.size()>1) return cout<<"NOT UNIQUE",0;

    s[brisem[0]]=0;

    string ans;
    fff(i,1,n)
    {
        if (s[i]) ans.pb(s[i]);
        if ((int)ans.size()==n/2) break;
    }

    cout<<ans<<"\n";
}

//Note to self: Check for overflow

Compilation message (stderr)

friends.cpp: In member function 'void hesiranje::build(int)':
friends.cpp:82:48: warning: array subscript has type 'char' [-Wchar-subscripts]
   82 |         fff(i,1,n) pre[i]=((li)pre[i-1]*p+w[s[i]])%mod;
      |                                             ~~~^

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