Submission #1167537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167537		son2008	Three Friends (BOI14_friends)	C++20	100 / 100	163 ms	83088 KiB

friends

#include<bits/stdc++.h>
using namespace std;
#define task "task"
#define ii pair<int,int>
#define fi first
#define se second
#define int long long
#define ll long long
#define ld double
#define mp make_pair
#define lg2 30
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define base 29
#define eps 1e-8
int dx[]= {0LL,0LL,1,-1,1,1,-1,-1};
int dy[]= {1,-1,0LL,0LL,1,-1,1,-1};
const int maxn=2e6+5;
const int mod=1e9+7;
int n;
string s;
int hs[maxn],p[maxn],hn[maxn];
int gethash(int i,int j)
{
    return (hs[j]-hs[i-1]*p[j-i+1]+mod*mod)%mod;
}
int gethashn(int i,int j)
{
    return (hn[i]-hn[j+1]*p[j-i+1]+mod*mod)%mod;
}
void init()
{
    cin>>n>>s;
    s=' '+s;
    for(int i=n;i>=1;i--)hn[i]=(hn[i+1]*base+s[i]-'a'+1)%mod;
}
void tao()
{
    p[0]=1;
    for(int i=1;i<=n;i++)p[i]=(p[i-1]*base)%mod;
    for(int i=1;i<=n;i++)hs[i]=(hs[i-1]*base+s[i]-'a'+1)%mod;
}
vector<int>ans,gtri;
void push(int id,bool ok)
{
    if(!ok)ans.push_back(n-id+1);
    else ans.push_back(id);
}
void xet(bool ok)
{
    for(int i=1;i<=n/2;i++)
    {
        if(i==1)
        {
            if(gethash(i+1,n/2+1)==gethash(n/2+i+1,n))
            {
                push(i,ok);
                if(!ok)gtri.push_back(gethashn(i+1,n/2+1));
                else
                    gtri.push_back(gethash(i+1,n/2+1));
            }
            continue;
        }
        if(gethash(1,i-1)==gethash(n/2+2,n/2+i)
           &&gethash(i+1,n/2+1)==gethash(n/2+i+1,n))
        {
            push(i,ok);
            if(!ok)gtri.push_back(gethashn(n/2+2,n));
                else
                    gtri.push_back(gethash(n/2+2,n));
        }
    }
}
void process()
{
    if(n%2==0)
    {
        cout<<"NOT POSSIBLE";
        return;
    }
    tao();
    xet(false);
    reverse(s.begin(),s.end());
    s=' '+s;
    tao();
    xet(true);
    if(gethash(1,n/2)==gethash(n/2+2,n))ans.push_back(n/2+1),gtri.push_back(gethash(1,n/2));
    sort(gtri.begin(),gtri.end());
    gtri.erase(unique(gtri.begin(),gtri.end()),gtri.end());
    if(!ans.size())
    {
        cout<<"NOT POSSIBLE";
    }
    else if(gtri.size()>1)
    {
        cout<<"NOT UNIQUE";
    }
    else
    {
        int dem=0;
        for(int i=n;i>=1;i--)
        {
            if(i==ans[0])continue;
            dem++;
            cout<<s[i];
            if(dem==n/2)return;
        }
    }
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(fopen(task".inp","r"))
    {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    init();
    process();
    cerr <<endl<< "TIME : " << clock() * 0.001 << "s" << endl ;
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:117:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
friends.cpp:118:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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