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("%d\n",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("%d\n",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;
}
0 Comments