Submission #1213644

#TimeUsernameProblemLanguageResultExecution timeMemory
1213644i_love_springThree Friends (BOI14_friends)C++20
0 / 100
420 ms129648 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
void solve() {  
    int n;
    cin >> n;
    string s;
    cin >> s;
    if (n % 2 == 0) {
      cout << "NOT POSSIBLE";
      return;
    }
    set<int> ans;
    set<ar<int,2>> bugs;
    for (int i = 0; i < n / 2;i++) {
      if (s[i] != s[i + n / 2 + 1]) bugs.insert({i, i + n / 2 + 1});
    }
    auto bl = bugs;
    auto br = bugs;
    for (int i =  1; i <= n / 2;i++) {
      int l = n / 2 - i;
      int r = n / 2 + i;
      //cerr << l << " "  << l + n / 2 + 1 << " " << n / 2 -  i + 1 << "\n";
      if (s[l] != s[l + n / 2 + 1]) {
        bl.erase({l, l + n / 2 + 1});
      }
      if (s[n / 2 - i + 1] != s[l + n / 2 + 1]) {
        bl.insert({n / 2 - i + 1, s[l + n / 2 + 1]});
      }
   //   cerr << r << " "  << r -  n / 2 - 1 << " " << n / 2 +  i - 1 << "\n";
      if (s[r] != s[r -  n / 2 - 1]) {
        br.erase({ r - n / 2 - 1,r});
      }
      if (s[n / 2 + i - 1] != s[r - n / 2 - 1]) {
        br.insert({r - n / 2 - 1,n / 2 + i - 1 });
      }
      if (bl.empty()) ans.insert(l);
      if (br.empty()) ans.insert(r);
    }
    if (ans.size() > 1) cout << "NOT UNIQUE";
    else if (ans.empty()) cout << "NOT POSSIBLE";
    else {
      int cnt = 0,ok = 0;
      for (int i = 0; cnt < n / 2;i++) {
        if (ok == 0 && ans.count(i)) {
          ok = 1;
          continue;
        }
        cout << s[i];
        cnt++;
      }
    }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t = 1;
  //cin >> t;
  while (t--) {
    solve();
    cout << "\n";
  }
  return 0;
} 
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...