제출 #645365

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
645365		tvladm2009	세 명의 친구들 (BOI14_friends)	C++14	0 / 100	1107 ms	186536 KiB

friends

#include <bits/stdc++.h>
#define int ll

using ll = long long;

int const nmax = 2000001;
int const B = 257;
int const P = 1e9 + 7;

int powerb[1 + nmax];

class SegmentTree {
 private:
    struct Node {
      int value;
      int sz;
    };

    std::vector<Node> aint;
 public:
    SegmentTree(int n) {
      aint.resize(4 * n + 1);
    }

    Node join(Node lson, Node rson) {
      Node aux;
      aux.value = (1LL * rson.value * powerb[lson.sz] % P + lson.value) % P;
      aux.sz = lson.sz + rson.sz;
      return aux;
    }

    void build(std::string s, int v, int from, int to) {
      if(from == to)
        aint[v] = Node {s[from - 1], 1};
      else {
        int mid = (from + to) / 2;
        build(s, 2 * v, from, mid);
        build(s, 2 * v + 1, mid + 1, to);
        aint[v] = join(aint[2 * v], aint[2 * v + 1]);
      }
    }

    Node query(int v, int from, int to, int p, int q) {
      if(p > q)
        return Node {0, 0};
      else if(p <= from && to <= q)
        return aint[v];
      else {
        int mid = (from + to) / 2;
        Node qleft = query(2 * v, from, mid, p, std::min(mid, q));
        Node qright = query(2 * v + 1, mid + 1, to, std::max(p, mid + 1), q);
        return join(qleft, qright);
      }
    }
};

signed main() {
  std::ios_base::sync_with_stdio(0);
  std::cin.tie(0);

  int n;
  std::string s;
  std::cin >> n >> s;
  if(n % 2 == 0) {
    std::cout << "NOT POSSIBLE";
    return 0;
  }

  powerb[0] = 1;
  for(int i = 1;i <= nmax; i++)
    powerb[i] = 1LL * powerb[i - 1] * B % P;

  SegmentTree aint(n);
  aint.build(s, 1, 1, n);
  int pos = 0;
  int sz = (n - 1) / 2;
  for(int i = 1;i <= n; i++) {
    int prefix = 0, suffix = 0;
    if(i <= sz) {
      prefix = aint.join(aint.query(1, 1, n, 1, i - 1), aint.query(1, 1, n, i + 1, sz + 1)).value;
      suffix = aint.query(1, 1, n, n - sz + 1, n).value;
    } else {
      prefix = aint.query(1, 1, n, 1, sz).value;
      suffix = aint.join(aint.query(1, 1, n, sz + 1, i - 1), aint.query(1, 1, n, i + 1, n)).value;
    }
    if(prefix == suffix) {
      if(pos > 0) {
        std::cout << "NOT UNIQUE\n";
        return 0;
      }
      pos = i;
    }
  }

  if(pos == 0) {
    std::cout << "NOT POSSIBLE";
    return 0;
  }
  if(pos <= sz) {
    for(int i = n - sz;i < n; i++)
      std::cout << s[i];
  } else {
    for(int i = 0;i < sz; i++)
      std::cout << s[i];
  }
  return 0;
}

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