제출 #1269124

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1269124		zNatsumi	세 명의 친구들 (BOI14_friends)	C++20	100 / 100	44 ms	34624 KiB

friends

#include <bits/stdc++.h>

using namespace std;

using ull = unsigned long long;
const int base = 213;

int n;
string s;

struct _Hash{
  vector<ull> pw, ha;
  _Hash(){}
  _Hash(string &s){
    ha.resize(s.size());
    pw.resize(s.size()); pw[0] = 1;
    for(int i = 1; i <= n; i++){
      pw[i] = pw[i - 1] * base;
      ha[i] = ha[i - 1] * base + s[i] - 'A' + 1;
    }
  }
  ull get(int l, int r){
    return ha[r] - ha[l - 1] * pw[r - l + 1];
  }
  ull _merge(int l, int r, int x, int y){
    if(l > r) return get(x, y);
    if(x > y) return get(l, r);
    return get(l, r) * pw[y - x + 1] + get(x, y);
  }
};

_Hash ha;



int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
//  ifstream cin("test.inp"); ofstream cout("test.out");

  cin >> n >> s;
  if(!(n&1)) return cout << "NOT POSSIBLE", 0;

  s = " " + s;
  ha = _Hash(s);

  set<ull> dif;
  for(int i = 1; i <= n; i++){
    ull L, R;
    if(i == (n + 1)/2) L = ha.get(1, i - 1), R = ha.get(i + 1, n);
    else if(i < (n + 1)/2) L = ha._merge(1, i - 1, i + 1, n/2 + 1), R = ha.get(n/2 + 2, n);
    else L = ha.get(1, n/2), R = ha._merge(n/2 + 1, i - 1, i + 1, n);

    if(L == R) dif.insert(L);
  }
  if(!dif.size()) cout << "NOT POSSIBLE";
  else if(dif.size() > 1) cout << "NOT UNIQUE";
  else{
    for(int i = 1; i <= n; i++){
      ull L, R;
      if(i == (n + 1)/2) L = ha.get(1, i - 1), R = ha.get(i + 1, n);
      else if(i < (n + 1)/2) L = ha._merge(1, i - 1, i + 1, n/2 + 1), R = ha.get(n/2 + 2, n);
      else L = ha.get(1, n/2), R = ha._merge(n/2 + 1, i - 1, i + 1, n);

      if(L == R){
        int it = 0, cnt = 0;
        while(cnt < n/2){
          ++it;
          if(it == i) continue;
          ++cnt;
          cout << s[it];
        }
        return 0;
      }
    }
  }
}

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