Submission #841958

#	Time	Username	Problem	Language	Result	Execution time	Memory
841958		manizare	세 명의 친구들 (BOI14_friends)	C++17	0 / 100	319 ms	128356 KiB

friends

#include <bits/stdc++.h> 

#define int long long 
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int> 
#define int long long
using namespace std ;
mt19937 rng(time(0)) ;

const int maxn = 2e6 + 10 , pr[] = {71 , 73}; 
int pre[2][maxn] , pw[2][maxn] , mod[2] , ipw[2][maxn] ;
int po(int a, int b , int m ){
  if(b==0)return 1;
  int v= po(a , b/2 , m) ;
  v = v*v % m ;
  if(b&1) v = v*a % m ;
  return v; 
}

int hs(int i , int l , int r){
  return (pre[i][r] - pre[i][l-1] + mod[i]) * ipw[i][l-1] % mod[i] ; 
}

signed main(){
  ios_base::sync_with_stdio(false); cin.tie(NULL);
  int n ;
  string s;
  cin >> n >> s ;
  if(n % 2==0){
    cout << "NOT POSSIBLE\n";
    return 0 ;
  }
  vector <int> prime ;
  for(int i = 1e9 ; i <= 1e9 + 200 ; i++){
    bool ok = 1;
    for(int j = 2; j*j <= i ; j++){
      if(i%j==0)ok = 0 ;
    }
    if(ok)prime.pb(i) ;
  }
  mod[0] = prime[rng() % (int)prime.size()] ;
  mod[1] = prime[rng() % (int)prime.size()] ;
  for(int i =0; i < 2; i++){
    pw[i][0] = 1; 
    for(int j = 1; j < maxn ; j++){
      pw[i][j] = pw[i][j-1] * pr[i] % mod[i] ;
    }
    ipw[i][maxn-1] = po(pw[i][maxn-1] , mod[i]-2 , mod[i]) ;
    for(int j = maxn-2 ; j >= 0; j --){
      ipw[i][j] = ipw[i][j+1] * pr[i] % mod[i] ;    
    }
  }
  s = " " + s; 
  for(int i = 0 ; i < 2; i ++){
    for(int j =1 ; j <= n ; j++){
      pre[i][j] = (pre[i][j-1] + ((int)(s[j]-'A') + 1) * pw[i][j] % mod[i]) % mod[i] ; 
    }
  }
  vector <pair <int,pii> > vec; 
  for(int i =1 ; i <= n ; i++){
    bool ok =1; 
    int a[3] ;
    a[0] = a[1] = 0 ;
    for(int j =0 ; j < 2 ; j++){
      if(i == n/2+1 && hs(j , 1 , i-1) != hs(j , i+1 , n)){
        ok = 0;
      }
      if(i <= n/2 && hs(j , n/2+2 , n) != (hs(j , 1 , i-1) + hs(j , i+1 , n/2+1) * pw[j][i-1] % mod[j])%mod[j]){
        ok =0  ;
      }
      if(i >= n/2+2 && hs(j , 1 , n/2) != (hs(j , n/2+1 , i-1) + hs(j , i+1 , n) * pw[j][i-1] % mod[j])%mod[j]){
        ok = 0 ;
      }
      if(i <= n/2+1){
        a[j] = hs(j , n/2+2 , n) ;
      }else{
        a[j]= hs(j , 1 , n/2) ;
      }
    }
    if(ok == 1){
      vec.pb({i , {a[0] , a[1]}}) ;
    }
  }
  bool ok =0 ; 
  for(int i = 1; i  <vec.size() ; i++){
    if(vec[i].S != vec[i-1].S) ok = 1;
  }
  if(vec.size() ==0){
    cout << "NOT POSSIBLE\n";
    return 0 ;
  }
  if(ok){
    cout << "NOT UNIQUE\n";
    return 0 ;
  }
  string a ; 
  for(int i = 1; i <= n ; i++){
    if(i == vec[0].F)continue ;
    a += s[i] ;
  }
  for(int i =0 ; i < n/2 ;i++){
    cout << a[i] ; 
  }
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:88:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   for(int i = 1; i  <vec.size() ; i++){
      |                  ~~~^~~~~~~~~~~

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