Submission #42987

#	Time	Username	Problem	Language	Result	Execution time	Memory
42987		PolyAtomicIon	Three Friends (BOI14_friends)	C++14	100 / 100	407 ms	35956 KiB

friends

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

   ll 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;
   }

   unordered_map<ll,int> u;
   vector< pair<ll,int> > ans;

   set<char> t;

int main(){

   cin >> n;
   cin >> s;

   for(int i=0; i<n; i++){
      t.insert(s[i]);
   }

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

   if( t.size() == 1 ){
      for(int i=0; i<n/2; i++){
         cout << s[i];
      }
      return 0;
   }

   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 && u[(a1+b1)%mod] == 0 ){
         ans.pb( mp((a1+b1)%mod,md+1) );
         u[(a1+b1)%mod]=1;
      }

   }

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

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

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

      ll b1 = get_hash(cur,md-1);
      ll 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 && u[(a1+b1)%mod] == 0 ){
         ans.pb( mp((a1+b1)%mod,0) );
         u[(a1+b1)%mod]=1;
      }
      cur++;
   }
   /*
   9
   FROGGFROG
   NOT UNIQUE
   *//*
   cout << ans.size() << endl;
   for(int i=0; i<ans.size(); i++){
      cout << ans[i].first << ' ' << ans[i].second << endl;
   }*/
   if( ans.size() == 0 ){
      cout << "NOT POSSIBLE";
   }
   else if( ans.size() > 1 ){
      cout << "NOT UNIQUE";
   }
   else{
      int id = ans[0].second;
      cout << s.substr(id,md);
   }

   return 0;
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:38:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0; i<n; i++){
                  ^
friends.cpp:48:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0; i<n/2; i++){
                     ^
friends.cpp:55:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=1; i<=n; i++){
                  ^
friends.cpp:61:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=1; i<n; i++){
                  ^
friends.cpp:93:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=md; i<n; i++){
                   ^

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