Submission #41349

#	Time	Username	Problem	Language	Result	Execution time	Memory
41349		gabrielsimoes	Three Friends (BOI14_friends)	C++14	100 / 100	85 ms	5804 KiB

friends

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

typedef long long ll;
const string not_possible = "NOT POSSIBLE";
const string not_unique = "NOT UNIQUE";

const ll MOD = 1645333507;
const ll BASE = 137;

ll buildHash(int i, int len, string s) {
  ll result = 0;
  while (len--) result = (result * BASE + ll(s[i] - 'A')) % MOD;
  return result;
}

bool test(string a, string b) {
  vector<bool> pref(b.size(), false), suf(b.size(), false);

  for (int i = 0; i < a.size(); i++) {
    if (a[i] == b[i])
      pref[i] = true;
    else
      break;
  }

  for (int i = a.size() - 1; i >= 0; i--) {
    if (a[i] == b[i + 1])
      suf[i + 1] = true;
    else
      break;
  }

  for (int i = 0; i < b.size(); i++)
    if ((i == 0 || pref[i - 1]) && (i == (b.size() - 1) || suf[i + 1]))
      return true;

  return false;
}

int main() {
  int n, m;
  string s;

  cin >> n >> s;
  m = n / 2;

  if (n < 3 || n != m * 2 + 1) {
    cout << not_possible << endl;
    return 0;
  }

  bool equalParts = 1;
  for (int i = 0; i < m; i++)
    if (s[i] != s[m + 1 + i]) equalParts = false;

  if (equalParts) {
    cout << s.substr(0, m) << endl;
    return 0;
  }

  bool ansl = test(s.substr(0, m), s.substr(m, m + 1));
  bool ansr = test(s.substr(m + 1, m), s.substr(0, m + 1));

  if (ansl && ansr)
    cout << not_unique << endl;
  else if (ansl)
    cout << s.substr(0, m) << endl;
  else if (ansr)
    cout << s.substr(m + 1, m) << endl;
  else
    cout << not_possible << endl;
}

Compilation message (stderr)

friends.cpp: In function 'bool test(std::__cxx11::string, std::__cxx11::string)':
friends.cpp:20:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < a.size(); i++) {
                     ^
friends.cpp:34:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < b.size(); i++)
                     ^
friends.cpp:35:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if ((i == 0 || pref[i - 1]) && (i == (b.size() - 1) || suf[i + 1]))
                                       ^

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