Submission #938200

#	Time	Username	Problem	Language	Result	Execution time	Memory
938200		Muhammad_Aneeq	Three Friends (BOI14_friends)	C++17	100 / 100	59 ms	37628 KiB

friends

/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/

#include <iostream>
#include <set>
using namespace std;
#define int long long
int const base=997,mod=1e9+7,N=2000011;
int pw[N]={};
int power(int x,int y)
{
  return pw[y];
}
inline void solve()
{
  int n;
  cin>>n;
  string x;
  cin>>x;
  if (n%2==0)
  {
    cout<<"NOT POSSIBLE\n";return;
  }
  int hash[n+1]={};
  int sz=n/2;
  set<int>ans;
  int ind=0;
  for (int i=0;i<n;i++)
    hash[i+1]=(hash[i]*base+x[i]-'A'+1)%mod;
  for (int i=1;i<=(n+1)/2;i++)
  { 
    int z=hash[i-1];
    int f=sz-i+1;
    int g=((hash[i+f]-(hash[i]*power(base,f))%mod)+mod)%mod;
    z=(z*power(base,f)+g)%mod;
    int y=((hash[n]-(hash[i+f]*power(base,sz))%mod)+mod)%mod;
    if (z==y)
    {
      if (ans.find(z)==ans.end())
        ind=i;
      ans.insert(z);
      if (ans.size()>1)
      {
        cout<<"NOT UNIQUE\n";return;
      }
    }
  }
  for (int i=(n+1)/2;i<=n;i++)
  {
    int z=hash[sz];
    int y=((hash[i-1]-(hash[sz]*power(base,(i-1-sz)))%mod)+mod)%mod;
    int u=((hash[n]-(hash[i]*power(base,(n-i)))%mod)+mod)%mod;
    y=(y*power(base,(n-i))+u)%mod;
    if (y==z)
    {
      if (ans.find(z)==ans.end())
        ind=i;
      ans.insert(z);
      if (ans.size()>1)
      {
        cout<<"NOT UNIQUE\n";return;
      }
    }
  }
  if (ind==0)
  {
    cout<<"NOT POSSIBLE\n";return;
  }
  string g;
  int i=1;
  while (g.size()!=sz)
  {
    if (i==ind)
      i++;
    else
    {
      g+=x[i-1];i++;
    }
  }
  cout<<g<<endl;
}
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    pw[0]=1;
    for (int i=1;i<N;i++)
      pw[i]=(pw[i-1]*base)%mod;
        solve();
}

Compilation message (stderr)

friends.cpp: In function 'void solve()':
friends.cpp:74:18: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   74 |   while (g.size()!=sz)
      |          ~~~~~~~~^~~~

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