Submission #42970

#	Time	Username	Problem	Language	Result	Execution time	Memory
42970		PolyAtomicIon	Three Friends (BOI14_friends)	C++14	0 / 100	1079 ms	93044 KiB

friends

#include <iostream>
#include <cmath>
#include <cstdio>
#include <string>
#include <set>
#define N 2111111
#define ll unsigned long long
#define pb push_back
#define mp make_pair
using namespace std;

   int n;
   ll p = 31,h[N],pw[N];
   ll mod = 1e9+7;
   string s;

   inline ll get_hash(int l,int r){
      if( l > r )
         return 0;
      if( l == 0 )
         return h[r] % mod;
      else
         return (h[r] - h[l-1]+mod) % mod;
   }

   set< pair<ll,int> > ans;

int main(){

   cin >> n;
   cin >> s;

   pw[0] = 1;
   for(int i=1; i<=n; i++){
      pw[i] = pw[i-1];
      pw[i] = (pw[i]*p) % mod;
   }

   h[0] = s[0]-'A'+1;
   for(int i=1; i<n; i++){
      h[i] = h[i-1];
      h[i] = ( h[i] % mod + ((s[i] - 'A'+1)*pw[i]) % mod);
      h[i] %= mod;
   }

   int md = n/2;

   for(int i=0; i<=md; i++){

      ll a1 = get_hash(0,i-1);
      ll a2 = get_hash(md+1,md+1+i-1);
      a1 = (a1 * pw[md+1]) % mod;

      //cout << s.substr(0,i) << " " << s.substr(md+1,i) << " : ";

      ll b1 = get_hash(i+1,i+1+md-i-1);
      ll b2 = get_hash(md+1+i,md+1+i+md-i-1);
      b1 = (b1 * pw[md]) % mod;

      //cout << s.substr(i+1,md-i) << ' ' << s.substr( md+1+i,md-i ) << '\n';

      //cout << i << " : " << a1 << ' ' << a2 << ' ' << b1 << ' ' << b2 << '\n';

      if( a1 == a2 && b1 == b2 ){
         ans.insert( mp((a1+b1)%mod,md+1) );
      }

   }

   int cur = 0;
   for(int i=md; i<n; i++){

      int a1 = get_hash(0,cur-1);
      int a2 = get_hash(i-cur,i-1);
      a1 = (a1 * pw[md]) % mod;

      //cout << s.substr(0,cur) << " " << s.substr(i-cur,cur) << " : ";

      int b1 = get_hash(cur,md-1);
      int b2 = get_hash(i+1,n-1);
      b1 = (b1 * pw[md+1]) % mod;

      //cout << s.substr(cur,md-cur) << ' ' << s.substr( i+1,md-cur ) << '\n';

      //cout << i << " : " << a1 << ' ' << a2 << ' ' << b1 << ' ' << b2 << '\n';

      if( a1 == a2 && b1 == b2 ){
         ans.insert( mp((a1+b1)%mod,0) );
      }

      cur++;
   }

   if( ans.size() == 0 ){
      cout << "NOT POSSIBLE";
   }
   else if( ans.size() > 1 ){
      cout << "NOT UNIQUE";
   }
   else{
      int id = ans.begin() -> second;
      cout << s.substr(id,md);
   }

   return 0;
}

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