Submission #1269376

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269376		rtri	Three Friends (BOI14_friends)	C++20	0 / 100	29 ms	4156 KiB

friends

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

int n;
string u;
int letter = -1;

string run(bool in_a) {
  int astart = n / 2;
  int bstart = n / 2;
  if (in_a)
    bstart++;
  else
    astart++;

  int alen = 0, blen = 0;
  int aoff = 0, boff = 0;
  string sol = "";
  while (alen < n / 2 && blen < n / 2) {
    char alet = u[astart + alen + aoff];
    char blet = u[bstart + blen + boff];
    if (alet != blet) {
      if (0 < aoff + boff)
        return "";
      if (alet == letter && in_a) {
        aoff++;
        continue;
      } else if (blet == letter && !in_a) {
        boff++;
        continue;
      } else {
        return "";
      }
    }

    sol.push_back(alet);
    alen++;
    blen++;
  }

  return sol;
}

int main() {
  cin >> n >> u;

  vector<int> CNT(26);
  for (int c : u)
    CNT[c - 'A']++;

  for (int i = 0; i < CNT.size(); i++) {
    if (CNT[i] % 2 == 1) {
      if (letter == -1) {
        letter = i;
      } else {
        cout << "NOT POSSIBLE" << endl;
        return 0;
      }
    }
  }

  if (letter == -1) {
    cout << "NOT POSSIBLE" << endl;
    return 0;
  }

  letter += 'A';

  auto sol1 = run(false);
  auto sol2 = run(true);
  reverse(u.begin(), u.end());
  auto sol4 = run(false);
  auto sol3 = run(true);
  reverse(sol3.begin(), sol3.end());
  reverse(sol4.begin(), sol4.end());

  cerr << "SOL1 " << sol1 << " " << sol1.size() << endl;
  cerr << "SOL2 " << sol2 << " " << sol2.size() << endl;
  cerr << "SOL3 " << sol3 << " " << sol3.size() << endl;
  cerr << "SOL4 " << sol4 << " " << sol4.size() << endl;

  if (sol1 == "" && sol2 == "" && sol3 == "" && sol4 == "")
    cout << "NOT POSSIBLE" << endl;
  else if (sol1 == sol3 && sol2 == "" && sol4 == "")
    cout << sol1 << endl;
  else if (sol2 == sol4 && sol1 == "" && sol3 == "")
    cout << sol2 << endl;
  else if (sol1 == sol2 && sol2 == sol3 && sol3 == sol4)
    cout << sol2 << endl;
  else
    cout << "NOT UNIQUE" << endl;

  return 0;
}

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