interesting twist

Revision en1, by singh1495, 2018-09-08 17:42:04

You are given an array A of length N. For any given integer X, you need to find an integer Z strictly greater than X such that Z is not present in the array A. You need to minimise the value of Z.

Input format :

First line : Two space seperated integers N and Q denoting the number of elements in array A and the number of queries respectively Second line : N space seperated integers denoting the array elements Next Q lines : Each line consists of an integer X Output fomat :

Print Q lines, each line denoting the answer to the corresponding query. Constraints :

Sample Input 5 2 2 7 5 9 15 3 9 Sample Output 4 10 Explanation For the first query, the minimum element greater than 3 and not present in the given array is 4. Similarly, for the second query, the answer is 10.

------------------------------------------------------------------------ for this problem i write this code

/*--.--.--.--.--.--.--.--.--.--.--.--.--* * By-Rohit Singh * * CS , MNNIT Allahabad * * [email protected] * --.--.--.--.--.--.--.--.--.--.--.--.--/

include

include

include

include

include

include

include

include

include

include

include

include <limits.h>

include <assert.h>

//#include using namespace std;

define mp make_pair

define pb push_back

define X first

define Y second

define null NULL

define ll long long

define llu unsigned long long

define MAX 200005

define mod 1000000007

define inf 1e16

define pp pair <int, int>

typedef double db; typedef long double ldb; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair <ll, int> pli; typedef pair <ldb, ldb> pdd;

define all(v) (v).begin(),(v).end()

const db PI = 3.141592653589793238;

define abs(x) ((x)>0?(x):-(x))

//#define pop pop_back()

define scan(x) scanf("%d",&x)

define print(x) printf("%d\n",x)

define scanll(x) scanf("%lld",&x)

define printll(x) printf("%lld\n",x)

define rep(i,n) for(int i=0;i<n;i++)

define REP(i,a,b) for(int i=a;i<=b;i++)

define PER(i,a,b) for(int i=b;i>=a;i--)

ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} //**********************************************HAPPY CODDING*****************************************************// int N; ll arr[MAX]; map<ll, int> hsh;

ll solve(int beg, int end, ll x) { int fst = beg; ll save = x; while (beg <= end) { int mid = (beg+end)>>1; ll get = mid-fst; ll act = arr[mid]-x; if (get == act) { save = arr[mid]; beg = mid+1; } else { end = mid-1; } } return save+1; } int main() {

int Q, ind = 0;
ll x, num;
scan(N);
scan(Q);
rep(i,N)  {
    scanll(num);
    if (!hsh[num])  {
       hsh[num] = ind+1;
       arr[ind++] = num;
    }  
}   
N = ind;
sort(arr, arr+N);
while (Q--)  {
    scanll(x);
    if (hsh[x+1])  {
       printll(solve(hsh[x+1]-1, N-1, x+1));
    }
    else  {
       printll(x+1);
    }

}
return 0;

}

can anyone tell me where it is failing thanx in advance

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English singh1495 2018-09-08 17:45:56 2202
en1 English singh1495 2018-09-08 17:42:04 3211 Initial revision (published)