제출 #645370

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

friends

#include <bits/stdc++.h>

using ll = long long;

int const nmax = 2000001;
int const B = 257;
int const P = 666013;

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 = 1001;i <= 1001; 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