제출 #42942

#제출 시각아이디문제언어결과실행 시간메모리
42942ruhanhabib39Three Friends (BOI14_friends)C++14
100 / 100
91 ms21788 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...