(15492) 뒤집기

https://www.acmicpc.net/problem/15492

 

 

 

뒤집기 K 문제의 힌트란에 이 문제를 먼저 풀고 오라고 적혀 있다. 그런데 이 문제의 티어가 더 높다.

이쪽은 서버 종료 직전이라 급해서 옛날 코드를 그대로 가져와서 뒤집기 K와는 코드 스타일이 조금 다르다.

사전 순으로 K번째 수열을 찾아야 했던 이전 문제와는 다르게 이 문제는 1번째 수열을 찾으면 되므로, O(N log N)으로 전체를 정렬할 필요 없이 맨 앞부터 배열을 O(N)으로 순회하며 가장 앞선 순열만 찾아주면 된다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#define p 524287
#define mod 998244353
using namespace std;

long getHash(vector<long>& hash,vector<long>& base, int l, int r){
  long ret= (hash[r] - hash[l-1] * base[r-l+1]) % mod;
  
  return (ret<0) ? ret+mod : ret;
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  int n_= 2*n-1;
  vector<int> v(n);
  vector<long> hash(n_), base(n_);
  
  for(int i=0;i<n;i++)  cin >> v[i];
  
  reverse(v.begin(), v.end());
  v.insert(v.end(), v.begin(), v.end());
  
  base[0]= 1;
  for(int i=1;i<n_;i++){
    hash[i]= (hash[i-1] * p + v[i]) % mod;
    base[i]= (base[i-1] * p) % mod;
  }
  
  int ans= 1;
  for(int i=2;i<n;i++){
    int l= 0, r= n;
    
    while(l<r){
      int mid= (l+r)/2;
      
      long a= getHash(hash, base, ans, ans+mid), b= getHash(hash, base, i, i+mid);
      
      if(a==b)  l= mid+1;
      else  r= mid;
    }
    
    if(l==n)  continue;
    else if(v[ans+l] > v[i+l])  ans= i;
  }
  
  for(int i=ans,j=0;j<n;j++){
    cout << v[i+j] << " ";
  }
  
  return 0;
}