Hello Everybody , Recently I was learning Binary Search and tried to to solve thsi problem using it. -- Link to the problem. My solution is like the one given in step 2 of binary search in codeforces edu by pashka
I have a good function to check if the people are enough to reach the desired place. in the beginning the l is 0 and the r is 1. then I continue multiplying r by 2 unless i reach a solution (r is definitely true ) then I binary search for the answer. But my program gives time limit exceeded.
My full solution
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;
const char newl='\n';
#define ll long long
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define mp make_pair
#define debug(x) cout << (#x) << "'s value is " << (x) << newl
typedef long long int lld;
const int MAX_N = 1e5 + 1;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
void setIO(string name = "") {
cin.tie(0)->sync_with_stdio(0); // see /general/fast-io
if (sz(name)) {
freopen((name+".in").c_str(), "r", stdin); // see /general/io
freopen((name+".out").c_str(), "w", stdout);
}
}
bool isPrime(int x) {
if(x<2){
return false;
}
for (int d = 2; d * d <= x; d++) {
if (x % d == 0)
return false;
}
return true;
}
typedef unsigned long long int ulli;
vector<ulli> sieve(ulli n)
{
vector<bool> prime(n+1,true);
prime[0] = false;
prime[1] = false;
int m = sqrt(n);
for (ulli p=2; p<=m; p++)
{
if (prime[p])
{
for (ulli i=p*2; i<=n; i += p)
prime[i] = false;
}
}
vector<ulli> ans;
for (int i=0;i<n;i++)
if (prime[i])
ans.push_back(i);
return ans;
}
bool isZero(ulli i)
{
return i == 0;
}
vector<ulli> sieveRange(ulli start,ulli end)
{
vector<ulli> s1 = sieve(start);
vector<ulli> s2 = sieve(end);
vector<ulli> ans(end-start);
set_difference(s2.begin(), s2.end(), s1.begin(),
s2.end(), ans.begin());
vector<ulli>::iterator itr =
remove_if(ans.begin(),ans.end(),isZero);
ans.resize(itr-ans.begin());
return ans;
}
int findpos(int arr[],int a,int n){
for(int i = 0;i<n;i++){
if(arr[i]==a){
return i;
}
}
return -1;
}
void arrxqc(int arr[], int le){
for(int my_var = 0;my_var<le;my_var++){
cout<<arr[my_var]<<" ";
}
cout<<newl;
}
// Main code starts here
int more(int a,int b,int c,int curr,int pieces){
if(curr==0){
return 1;
}
if(curr<0){
;
}
else{
pieces = pieces+max(more(a,b,c,curr-a,pieces),max(more(a,b,c,curr-b,pieces),more(a,b,c,curr-c,pieces)));
}
return pieces;
}
const int N = 4e3 + 10;
bool good(ll checker,ll n, vector<int> all_x,vector<int> all_y,vector<int> all_p,vector<int> all_q,vector<int> all_r,ll c){
if(c!=0){
vector<int>::iterator curr_x = all_x.begin();
vector<int>::iterator curr_y = all_y.begin();
vector<int>::iterator curr_p = all_p.begin();
vector<int>::iterator curr_q = all_q.begin();
vector<int>::iterator curr_r = all_r.begin();
for(int i = 0;i<n;i++){
if(i==(*curr_x)){
checker = checker-(*curr_y);
curr_x++;
curr_y++;
}
if(i==(*curr_p)){
if(checker>=(*curr_q)){
checker = checker+(*curr_r);
}
curr_p++;
curr_q++;
curr_r++;
}
if(checker<=0){
return false;
}
}
return true;
}
else{
vector<int>::iterator curr_x = all_x.begin();
vector<int>::iterator curr_y = all_y.begin();
for(int i = 0;i<n;i++){
if(i==(*curr_x)){
checker = checker-(*curr_y);
curr_x++;
curr_y++;
}
if(checker<=0){
return false;
}
}
return true;
}
}
void answer(int test){
ll x;
cin>>x;
ll b;
cin>>b;
vector<int> all_x;
vector<int> all_y;
all_x.resize(b);
all_y.resize(b);
for(int i = 0;i<b;i++){
cin>>all_x[i]>>all_y[i];
}
ll c;
cin>>c;
vector<int> all_p;
vector<int> all_q;
vector<int> all_r;
all_p.resize(c);
all_q.resize(c);
all_r.resize(c);
for(int i = 0;i<c;i++){
cin>>all_p[i]>>all_q[i]>>all_r[i];
}
ll l = 0;
ll r = 1;
while(!good(r,x,all_x,all_y,all_p,all_q,all_r,c)){
r = r*2;
}
ll ans = -1;
while(r>l+1){
ll mid = (l+r)/2;
if(good(mid,x,all_x,all_y,all_p,all_q,all_r,c)){
r = mid;
ans = mid;
}
else{
l = mid;
}
}
cout<<ans<<newl;
}
int main(){
auto start = chrono::steady_clock::now();
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int test = 1;
cin>>test;
int curr = 1;
while(test--){
answer(curr);
curr++;
}
auto end = chrono::steady_clock::now();
auto diff = end - start;
//cout <<"Duration is "<<chrono::duration <double, milli> (diff).count() << " ms" << endl;
}
Only the good function
bool good(ll checker,ll n, vector<int> all_x,vector<int> all_y,vector<int> all_p,vector<int> all_q,vector<int> all_r,ll c){
if(c!=0){
vector<int>::iterator curr_x = all_x.begin();
vector<int>::iterator curr_y = all_y.begin();
vector<int>::iterator curr_p = all_p.begin();
vector<int>::iterator curr_q = all_q.begin();
vector<int>::iterator curr_r = all_r.begin();
for(int i = 0;i<n;i++){
if(i==(*curr_x)){
checker = checker-(*curr_y);
curr_x++;
curr_y++;
}
if(i==(*curr_p)){
if(checker>=(*curr_q)){
checker = checker+(*curr_r);
}
curr_p++;
curr_q++;
curr_r++;
}
if(checker<=0){
return false;
}
}
return true;
}
else{
vector<int>::iterator curr_x = all_x.begin();
vector<int>::iterator curr_y = all_y.begin();
for(int i = 0;i<n;i++){
if(i==(*curr_x)){
checker = checker-(*curr_y);
curr_x++;
curr_y++;
}
if(checker<=0){
return false;
}
}
return true;
}
}
The mian function
void answer(int test){
ll x;
cin>>x;
ll b;
cin>>b;
vector<int> all_x;
vector<int> all_y;
all_x.resize(b);
all_y.resize(b);
for(int i = 0;i<b;i++){
cin>>all_x[i]>>all_y[i];
}
ll c;
cin>>c;
vector<int> all_p;
vector<int> all_q;
vector<int> all_r;
all_p.resize(c);
all_q.resize(c);
all_r.resize(c);
for(int i = 0;i<c;i++){
cin>>all_p[i]>>all_q[i]>>all_r[i];
}
ll l = 0;
ll r = 1;
while(!good(r,x,all_x,all_y,all_p,all_q,all_r,c)){
r = r*2;
}
ll ans = -1;
while(r>l+1){
ll mid = (l+r)/2;
if(good(mid,x,all_x,all_y,all_p,all_q,all_r,c)){
r = mid;
ans = mid;
}
else{
l = mid;
}
}
cout<<ans<<newl;
}
Comments (0)
