Submission #91720

#	Time	Username	Problem	Language	Result	Execution time	Memory
91720		Mercenary	Three Friends (BOI14_friends)	C++14	0 / 100	1068 ms	69060 KiB

friends

#include<bits/stdc++.h>

using namespace std;
#define taskname "TEST"
#define pb	push_back
typedef long double ld;
typedef long long ll;
const int maxn = 2e6 + 5;
const int mod = 1e9 + 69;
const int base = 33;

int n , H[maxn] , P[maxn];
string s;

int Get(int i , int j)
{
    return (H[j] - (ll)H[i - 1] * P[j - i + 1] + (ll)mod * mod) % mod;
}

int Get(int i , int j , int del)
{
    if(i > del || j < del)return Get(i,j);
    if(i == del)return Get(i+1,j);
    if(j == del)return Get(i,j-1);
    int lef = Get(i,del-1);
    int rig =  Get(del+1,j);
    return ((ll)lef * base + rig) % mod;
}

map<int,pair<int,int>> mmap;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	if(fopen(taskname".INP","r"))
        freopen(taskname".INP", "r",stdin) ,
        freopen(taskname".OUT", "w",stdout);
    cin >> n >> s;
    if(n % 2 == 0)return cout << "NOT POSSIBLE" , 0;
    s = " " + s;
    set<int> v;
    P[0] = 1;
    for(int i = 1 ; i <= n ; ++i)P[i] = (ll)P[i - 1] * base % mod;
    for(int i = 1 ; i <= n ; ++i)H[i] = ((ll)H[i - 1] * base + s[i] - 'A') % mod;
    for(int i = 1 ; i <= n ; ++i)
    {
        int lef = Get(1 , n / 2 + (i <= n / 2) , i);
        int rig = Get(n / 2 + 2 - (i > n / 2 + 1) , n , i);
        if(lef == rig)v.insert(lef);
//        cout << lef << " " << rig << endl;
        if(i <= n / 2)mmap[lef] = make_pair(n / 2 + 2 , n);
        else mmap[lef] = make_pair(1 , n / 2);
    }
    if(v.size() == 0)return cout << "NOT POSSIBLE" , 0;
    if(v.size() > 1)return cout << "NOT UNIQUE" , 0;
    cout << s.substr(mmap[*v.begin()].first,mmap[*v.begin()].second);
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:37:44: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(taskname".INP", "r",stdin) ,
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
         freopen(taskname".OUT", "w",stdout);
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
friends.cpp:37:44: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]

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