HackerEarth Sherlock and Numbers problem solution

In this HackerEarth Sherlock and Numbers problem solution Watson gives to Sherlock a bag of numbers [1, 2, 3 … N] and then he removes K numbers A1, A2 … AK from the bag. He now asks Sherlock to find the P’th smallest number in the bag.

HackerEarth Sherlock and Numbers problem solution.

#include<bits/stdc++.h>
#define assn(n,a,b) assert(n<=b && n>=a)
using namespace std;
#define pb push_back
#define mp make_pair
#define clr(x) x.clear()
#define sz(x) ((int)(x).size())
#define F first
#define S second
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,b) for(i=0;i<b;i++)
#define rep1(i,b) for(i=1;i<=b;i++)
#define pdn(n) printf("%dn",n)
#define sl(n) scanf("%lld",&n)
#define sd(n) scanf("%d",&n)
#define pn printf("n")
typedef pair<int,int> PII;
typedef vector<PII> VPII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long LL;
#define MOD 1000000007
LL mpow(LL a, LL n) 
{LL ret=1;LL b=a;while(n) {if(n&1) 
    ret=(ret*b)%MOD;b=(b*b)%MOD;n>>=1;}
return (LL)ret;}
#define MAXK 100000
#define MAXN 1000000000
int ar[MAXK];
int get(int n, int k){
    int i=0;
    while(i<k and ar[i]<=n)i++;
    return n-i;
}
int main()
{
    int t;
    sd(t);
    assn(t,1,10);
    while(t--){
        int n,k,p,s=0;
        sd(n),sd(k),sd(p);
        assn(n,1,MAXN);
        assn(k,0,MAXK);
        assn(p,1,n);
        for(int i=0; i<k; i++)
            sd(ar[i]);
        sort(ar,ar+k);
        int l=0,r=n,mid;
        if(get(r,k)<p){
            pdn(-1);
            continue;
        }
        while(r-l>1){
            mid=(r+l)/2;
            int q=get(mid,k);
            if(q<p)l=mid;
            else r=mid;
        }
        pdn(l+1);
    }
    return 0;
}

Second solution

#include <cstdio>
#include <cmath>
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
#include <map>
#include <cassert>
#include <string>
#include <cstring>
#include <queue>

using namespace std;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define S(x) scanf("%d",&x)
#define S2(x,y) scanf("%d%d",&x,&y)
#define P(x) printf("%dn",x)
#define all(v) v.begin(),v.end()
#define sz size()

typedef long long int LL;
typedef pair<int, int > pii;
typedef vector<int > vi;

set<int > s;
vi v;

int lessThan(int x) {

  int lo = 0, hi = (int)v.size() - 1;
  int res = -1;

  while(lo <= hi) {
    int mi = (lo + hi) >> 1;
    if(v[mi] <= x) {
      res = mi;
      lo = mi + 1;
    } else {
      hi = mi - 1;
    }
  }

  return res + 1;
}

int main() {
  int t;
  S(t);

  assert(t >= 1 && t <= 10);

  while(t--) {
    int n,k,p;
    scanf("%d%d%d",&n,&k,&p);
    assert(n >= 1 && n <= 1000000000);
    assert(k >= 1 && k <= min(n, 100000));
    assert(p >= 1 && p <= 1000000000);
    s.clear();
    v.clear();
    rep(i,0,k) {
      int x;
      S(x);
      assert(x >= 1 && x <= n);
      if(s.find(x) == s.end()) {
        v.push_back(x);
        s.insert(x);
      }
    }

    sort(all(v));
    int lo = 1, hi = 2*n;

    int ans = 0;
    while(lo <= hi) {
      int mi = (lo + hi * 1LL) / 2;
      int x = lessThan(mi);

      int tot = mi - x;
      if(tot >= p) {
        ans = mi;
        hi = mi - 1;
      } else {
        lo = mi + 1;
      }
    }
    if(ans > n) ans = -1;
    P(ans);
  }

  return 0;
}

coding problems solutions