Submission #42942

#	Time	Username	Problem	Language	Result	Execution time	Memory
42942		ruhanhabib39	Three Friends (BOI14_friends)	C++14	100 / 100	91 ms	21788 KiB

friends

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5+1;

int N;
string inp;

// [i, j), [l, r)
bool oka(int i, int j, int l, int r) {
   while(i < j) {
      while(l < r && inp[i] != inp[l]) l++;
      if(l >= r) break;
      i++; l++;
   }
   return i == j;
}

string solve() {
   const string notPossible = "NOT POSSIBLE";
   const string notUnique = "NOT UNIQUE";

   if(N % 2 == 0) return notPossible;
   int m = N / 2;
   bool okA = oka(0, m, m, N);
   bool okB = oka(m+1, N, 0, m+1);
   if(!okA && !okB) return notPossible;
   if(okA && okB && inp.substr(0, m) != inp.substr(m+1, m)) return notUnique;
   if(okA) return inp.substr(0, m);
   return inp.substr(m+1, m);
}

int main() {
   cin >> N >> inp;
   cout << solve() << endl;
}

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