Submission #778794

#	Time	Username	Problem	Language	Result	Execution time	Memory
778794		raysh07	Three Friends (BOI14_friends)	C++17	100 / 100	292 ms	69776 KiB

friends

#include <bits/stdc++.h>
 
using namespace std;
struct Hash{
    long long a = 911382323 , mod = 972663749;
    long long h[2000005],p[2000005];
    void has(string s){
        h[0] = 0 , p[0] = 1;
        for(int i = 0;i<s.size();i++){
            h[i+1] = (h[i]*a+((s[i]-'A')+1))%mod;
        }
        for(int i = 1;i<=2000002;i++){
            p[i] = (p[i-1]*a)%mod;
        }
    }
    long long q(int l,int r){
        if(l>r)return 0;
        return(((h[r]-h[l-1]*p[r-l+1])%mod)+mod)%mod;
    }
}hsh1,hsh2;
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int len;cin>>len;
    string s;cin>>s;
    hsh2.a =37 , hsh2.mod = 1000000007;
    hsh1.a =911382323,hsh2.mod = 972663749;
    hsh1.has(s);hsh2.has(s);
    int an = -1;
    long long fii1 = -1 , fii2 = -1;
    bool uni = 1;
    for(int i = 1;i<=len;i++){
        long long fi1 = 0, fi2 = 0 , se1 = 0, se2 = 0;
        if(i>len/2){
            fi1 = hsh1.q(1,len/2);
            fi2 = hsh2.q(1,len/2);
            long long rem = (len/2)-(i-(len/2+1));
            se1 = hsh1.q(len/2+1,i-1);
            se2 = hsh2.q(len/2+1,i-1);
            se1*=hsh1.p[rem];
            se1%=hsh1.mod;
            se2*=hsh2.p[rem];
            se2%=hsh2.mod;
            se1+=hsh1.q(i+1,len);
            se1%=hsh1.mod;
            se2+=hsh2.q(i+1,len);
            se2%=hsh2.mod;
        }else{
            long long rem = (len/2)-(i-1);
            fi1 = hsh1.q(1,i-1);
            fi2 = hsh2.q(1,i-1);
            fi1*=hsh1.p[rem];
            fi1%=hsh1.mod;
            fi2*=hsh2.p[rem];
            fi2%=hsh2.mod;
            fi1+=hsh1.q(i+1,len/2+1);
            fi1%=hsh1.mod;
            fi2+=hsh2.q(i+1,len/2+1);
            fi2%=hsh2.mod;
            se1 = hsh1.q(len/2+2,len);
            se2 = hsh2.q(len/2+2,len);
        }
        if(fi1==se1&&fi2==se2){
            if(an==-1){
                fii1 = fi1;
                fii2 = fi2;
            }else{
                if(fii1!=fi1||fii2!=fi2){
                    uni = 0;
                }
            }
            an = i;
        }
    }
    if(an==-1){
        cout<<"NOT POSSIBLE\n";
    }else{
        if(!uni)cout<<"NOT UNIQUE\n";
        else{
            int rev = 0;
            for(int i = 0;i<s.size();i++){
                if(i+1==an)continue;
                rev++;
                if(rev<=len/2){
                    cout<<s[i];
                }
            }
            cout<<endl;
        }
    }
}

Compilation message (stderr)

friends.cpp: In member function 'void Hash::has(std::string)':
friends.cpp:9:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |         for(int i = 0;i<s.size();i++){
      |                       ~^~~~~~~~~
friends.cpp: In function 'int main()':
friends.cpp:80:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |             for(int i = 0;i<s.size();i++){
      |                           ~^~~~~~~~~

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