PAYBILL - EDITORIAL

problem link :

Practice
Contest

Author: Pratik Suryawanshi

Editorialist: Pratik Suryawanshi

DIFFICULTY:

Moderate

PREREQUISITES:

Binary Search

PROBLEM:

Chef and his N number of friends [1,2,3,4,……,N] go to the hotel and ordered a lot of food
after finishing a food waiter give a bill amount of X . each friend of chef have certain
amount of money given in array. chef decided to pay bill by taking money from any 2 friends only
so print distinct position of any 2 members from which he will take money to pay X amount
of bill. if not possible to pay X amount of money from 2 members print “-1”.

QUICK EXPLANATION:

print the distinct position of any two elements of array whose sum is X

EXPLANATION:

approach 1: using 2d array , add any two elements of array, if sum == x , print i,j.
approach 2: using map<int,int> add all pair of number of array thrn use binary search
, if x fount print int,int position

SOLUTIONS:

Setter's Solution

#include<bits/stdc++.h>

using namespace std;

#define all(c) c.begin(),c.end()
#define gcd(a,b) __gcd(abs(a),abs(b))
#define lcm(a,b) (((a)/(__gcd(a,b)))(b))
#define isodd(a) ((a)&1)
#define iseven(a) !((a)&1)
#define sync() ios_base::sync_with_stdio(false),cin.tie(nullptr)
#define pii pair<int,int>
#define pll pair<long long, long long>
#define tr(it,c) for(auto & it : (c))
#define rtr(it,c) for(auto it = (c).rbegin(); it != (c).rend(); it++)
#define ll long long
#define endl “\n”
#define abs(x) (((x) < 0) ? -(x) : (x))
#define clr(x,y) memset((x),(y),sizeof(x))
#define popcount(x) __builtin_popcount(x)
#define fileout(x) freopen(x, “w”, stdout)
#define filein(x) freopen(x, “r”,stdin)
#define error(x) freopen(x,“w”,stderr)
#define sqr(x) ((x)
(x))
#define cube(x) ((x)(x)(x))
#define inf 1<<30
#define mod 1000000007
#define pi acos(-1.)
#define valid(x,y,row,col) (((x) >= 0 and (x) < row) and ((y) >= 0 and (y) < col))
#define debug(…) fprintf(stderr, VA_ARGS), fflush(stderr)
#define timer(d) for(long blockTime=NULL;(blockTime==NULL?(blockTime=clock())!=NULL:false); debug(“%s:%.4fs”,d,(double)(clock()-blockTime)/CLOCKS_PER_SEC))

int x4[] = {0,0,1,-1};
int y4[] = {1,-1,0,0};

int main()
{
int t;
cin >> t;
while(t–)
{
sync();
int n,k;
cin >> n >> k;
vector ara(n),nexter;
map<int,int> counter;
tr(i,ara){
cin >> i;
counter[i]++;
}
nexter = ara;
sort(all(ara));
int a = -1,b = -1;
for(int i = 0; i < n; ++i){
if(binary_search(all(ara),k-nexter[i])){
if(k-nexter[i] == nexter[i]){
if(counter[nexter[i]] > 1){
a = i;
b = nexter[i];
break;
}
}else{
a = i;
b = k-nexter[i];
break;
}
}
}
if(a != -1 and b != -1){
cout << a+1 << " ";
for(int i = 0; i < n; ++i){
if(b == nexter[i] and i != a){
cout << i+1 << endl;
break;
}
}
}else{
cout << -1 << endl;
}
}
return 0;
}