Advertisement
YEZAELP

TOI13: Cats

Jul 12th, 2020
91
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.96 KB | None
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using lli = long long;
  5. const lli INF = 2e18;
  6. vector <lli> cat;
  7.  
  8. bool move(lli mid,int n){
  9.     int bf = -1;
  10.     set <lli> keep;
  11.     for(int i=0;i<n;i++){
  12.         if(cat[i] <= mid) continue;
  13.         if(bf == cat[i]) {
  14.             keep.erase(keep.find(bf));
  15.             bf = -1;
  16.         }
  17.         else{
  18.             bf = cat[i];
  19.             if(keep.find(cat[i]) != keep.end()) return false;
  20.             keep.insert(cat[i]);
  21.         }
  22.     }
  23.     return true;
  24. }
  25.  
  26. int main(){
  27.  
  28.     int n;
  29.     lli l=0, r=-INF,mn=INF;
  30.     scanf("%d",&n);
  31.  
  32.     for(int i=0;i<n;i++){
  33.         lli x;
  34.         scanf("%lld",&x);
  35.         cat.push_back(x);
  36.         r = max(r,x);
  37.     }
  38.  
  39.     while(l <= r){
  40.         lli mid = (l+r)/2;
  41.         if(move(mid,n)){
  42.             r = mid-1;
  43.             mn = min(mn, mid);
  44.  
  45.         }
  46.         else
  47.             l = mid+1;
  48.     }
  49.     printf("%lld",mn);
  50.  
  51.     return 0;
  52. }
Advertisement
RAW Paste Data Copied
Advertisement