Submission #574540

#	Time	Username	Problem	Language	Result	Execution time	Memory
574540		MohammadAghil	Three Friends (BOI14_friends)	C++14	100 / 100	180 ms	74784 KiB

friends

      #include <bits/stdc++.h>
//   #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
    using namespace std;
  typedef long long ll;
   typedef pair<int, int> pp;
    #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
      #define per(i,r,l) for(int i = (r); i >= (l); i--)
        #define rep(i,l,r) for(int i = (l); i < (r); i++)
           #define all(x) x.begin(), x.end()
              #define sz(x) (int)(x).size()
                  #define pb push_back
                      #define ss second
                           #define ff first
                                   void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 1e5 + 1, maxk = 101, lg = 21, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}

struct PolyHash{
     #define __cnt 2
     ll mod[__cnt] = {998244353, ll(1e9) + 7}, p = 9973;
     vector<ll> pw[__cnt], hsh[__cnt];
     PolyHash(){
          rep(i,0,__cnt) pw[i].pb(1);
     }
     PolyHash(vector<int> a){
          int n = sz(a);
          rep(i,0,__cnt){
               pw[i].assign(n + 1, 1);
               rep(j,1,n + 1) pw[i][j] = p*pw[i][j-1]%mod[i];
               hsh[i].assign(n, a[0]);
               rep(j,1,n) hsh[i][j] = p*hsh[i][j-1]%mod[i] + a[j], hsh[i][j] %= mod[i];
          }
     }
     void add(int k){
          rep(i,0,__cnt){
               pw[i].pb(pw[i].back()*p%mod[i]);
               hsh[i].pb(((sz(hsh[i])?hsh[i].back():0)*p%mod[i] + k)%mod[i]);
          }
     }
     int get(int l, int r, int id = 0){
          return (hsh[id][r] - (l?hsh[id][l-1]:0)*pw[id][r - l + 1]%mod[id] + mod[id])%mod[id];
     }
     int get(int id = 0){ return get(0, sz(hsh[id])-1, id); }
     pp get2(int l, int r){
          return {get(l, r, 0), get(l, r, 1)};
     }
     pp get2(){ return get2(0, sz(hsh[0])-1); }
     vector<int> get_mul(int l, int r){
          vector<int> res;
          rep(i,0,__cnt) res.pb(get(l, r, i));
          return res;
     }
     vector<int> get_mul(){ return get_mul(0, sz(hsh[0])-1); }
};

int main(){
     cin.tie(0) -> sync_with_stdio(0); 
     int n; cin >> n;
     string s; cin >> s; PolyHash hsh(vector<int>(all(s)));
     if(n%2 == 0) return cout << "NOT POSSIBLE\n", 0;
     bool isl = false, isr = false;

     rep(i,n>>1,n){
          int dl = i - (n>>1);
          if(!dl || hsh.get(0, dl-1) == hsh.get(n>>1, (n>>1)+dl-1)){
               int dr = n - 1 - i;
               if(!dr || hsh.get(i+1, n-1) == hsh.get((n>>1)-dr, (n>>1)-1)){
                    isl = true;
                    break;
               }
          }
     }

     rep(i,0,(n>>1)+1){
          int dl = i;
          if(!dl || hsh.get(0, i-1) == hsh.get((n>>1)+1, (n>>1) + dl)){
               int dr = (n>>1)-i;
               if(!dr || hsh.get((n>>1)-dr+1, n>>1) == hsh.get((n>>1)+dl+1, n-1)){
                    isr = true;
                    break;
               }
          }
     }

     if(isl && isr){
          if(hsh.get(0,(n>>1)-1) == hsh.get((n>>1)+1, n-1)) cout << string(begin(s), begin(s) + (n>>1)) << '\n';
          else cout << "NOT UNIQUE\n";
     } else if(isl){
          cout << string(begin(s), begin(s) + (n>>1)) << '\n';
     } else if(isr){
          cout << string(begin(s)+(n>>1)+1, end(s)) << '\n';
     } else cout << "NOT POSSIBLE\n";
     return 0; 
}

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