Submission #231765

#	Time	Username	Problem	Language	Result	Execution time	Memory
231765		AlexLuchianov	Three Friends (BOI14_friends)	C++14	100 / 100	231 ms	21188 KiB

friends

#include <iostream>
#include <fstream>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const modulo = 998244353;
int const nmax = 2000005;
int const sigma = 26;
int pow[1 + nmax];
int pref[1 + nmax];

void computepow(){
  pow[0] = 1;
  for(int i = 1;i <= nmax; i++)
    pow[i] = 1LL * pow[i - 1] * sigma % modulo;
}

int extract(int x, int y){
  int d = (y - x + 1);
  return (modulo + pref[y] - 1LL * pref[x - 1] * pow[d] % modulo) % modulo;
}

int extract2(int x, int y, int skip){
  int result1 = extract(x, skip - 1);
  int result2 = extract(skip + 1, y);
  int d = (y - skip);
  return (1LL * result1 * pow[d] + result2) % modulo;
}
  std::string s;

void extractprint(int x, int y, int skip){
  for(int i = x; i <= y; i++)
    if(i != skip) {
      std::cout << (char)s[i];
    }
}

int main()
{
  computepow();
  int n;
  std::cin >> n;
  if(n % 2 == 0){
    std::cout << "NOT POSSIBLE\n";
    return 0;
  }
  std::cin >> s;
  s = "#" + s;
  for(int i = 1; i <= n; i++)
    pref[i] = (1LL * pref[i - 1] * sigma + s[i] - 'A') % modulo;

  int id = -1, pos = 0;

  for(int i = 1; i <= n; i++){
    int result, result2;
    if(i <= n / 2) {
      result = extract2(1, n / 2 + 1, i);
      result2 = extract2(n / 2 + 1, n, n / 2 + 1);
    } else {
      result = extract2(1, n / 2 + 1, n / 2 + 1);
      result2 = extract2(n / 2 + 1, n, i);
    }

    if(result == result2){
      if(id == -1) {
        pos = i;
        id = result;
      } else if(id != result){
        std::cout << "NOT UNIQUE\n";
        return 0;
      }
    }
  }

  if(id == -1)
    std::cout << "NOT POSSIBLE\n";
  else {
    if(pos <= n / 2)
      extractprint(1, n / 2 + 1, pos);
    else
      extractprint(1, n / 2, n / 2 + 1);
  }
  return 0;
}

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