## 13001 - Jumping Frogs

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### 13001 - Jumping Frogs

Use this thread to discuss this problem.
Check input and AC output for thousands of problems on uDebug!

draak_krijger
New poster
Posts: 1
Joined: Mon Mar 21, 2016 6:54 pm

### Re: 13001 - Jumping Frogs

i am trying this problem many times but i failed to get AC .
my approach is binary search on time .

mycode :

Code: Select all

``````
// Pre_code

#include <bits/stdc++.h>

#include <sstream>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <complex>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <string>
#include <utility>
#include <vector>
#include <algorithm>
#include <bitset>
#include <list>
#include <string.h>
#include <assert.h>
#include <time.h>
#include <fstream>
#include <numeric>
#include <cstring>

using namespace std ;

//define function

#define forln(i,a,n) for(int i=a ; i<n ; i++)
#define foren(i,a,n) for(int i=a ; i<=n ; i++)
#define forg0(i,a,n) for(int i=a ; i>n ; i--)
#define fore0(i,a,n) for(int i=a ; i>=n ; i--)
#define pb push_back
#define pp pop_back
#define clr(a,b) memset(a,b,sizeof(a))
#define sf1(a) scanf("%d",&a)
#define sf2(a,b) scanf("%d %d",&a,&b)
#define sf1ll(a) scanf("%lld",&a)
#define sf2ll(a,b) scanf("%lld %lld",&a,&b)
#define pii acos(-1.0)
#define jora_int pair<int,int>
#define jora_ll pair<long long,long long>
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define Max 15000000+9
#define sz 100000+7
#define Mod 1000000007
#define EPS 1e-10
#define ll long long
#define ull unsigned long long
#define fs first
#define sc second
#define wait system("pause")
#define sf scanf
#define pf printf
#define mp make_pair
#define ps pf("PASS\n")
#define Write freopen("C:\\Users\\RONIN-47\\Desktop\\input_output\\output.txt","w",stdout)
//debug

template<class T1> void deb(T1 e1)
{
cout<<e1<<endl;
}
template<class T1,class T2> void deb(T1 e1,T2 e2)
{
cout<<e1<<" "<<e2<<endl;
}
template<class T1,class T2,class T3> void deb(T1 e1,T2 e2,T3 e3)
{
cout<<e1<<" "<<e2<<" "<<e3<<endl;
}
template<class T1,class T2,class T3,class T4> void deb(T1 e1,T2 e2,T3 e3,T4 e4)
{
cout<<e1<<" "<<e2<<" "<<e3<<" "<<e4<<endl;
}
template<class T1,class T2,class T3,class T4,class T5> void deb(T1 e1,T2 e2,T3 e3,T4 e4,T5 e5)
{
cout<<e1<<" "<<e2<<" "<<e3<<" "<<e4<<" "<<e5<<endl;
}
template<class T1,class T2,class T3,class T4,class T5,class T6> void deb(T1 e1,T2 e2,T3 e3,T4 e4,T5 e5,T6 e6)
{
cout<<e1<<" "<<e2<<" "<<e3<<" "<<e4<<" "<<e5<<" "<<e6<<endl;
}

// moves

//int dx[]= {-1,-1,0,0,1,1};
//int dy[]= {-1,0,-1,1,0,1};
//int dx[]= {0,0,1,-1};/*4 side move*/
//int dy[]= {-1,1,0,0};/*4 side move*/
//int dx[]= {1,1,0,-1,-1,-1,0,1};/*8 side move*/
//int dy[]= {0,1,1,1,0,-1,-1,-1};/*8 side move*/
//int dx[]={1,1,2,2,-1,-1,-2,-2};/*night move*/
//int dy[]={2,-2,1,-1,2,-2,1,-1};/*night move*/

//close

// Not Solved

vector<ll>segment ;
vector<ll>::iterator it ;
jora_ll red[sz] , green[sz] , rd , gr ;
ll n , r , g ;

ll cal_red(ll tme)
{
ll tp , tp1 , mx1 = -1 , mn = -1 , mx2 = -1 ;
bool ok = 0 ;

rd = mp(-1,-1);

for(int i=0 ; i<r ; i++)
{
tp = red[i].fs + red[i].sc*tme ;

it = lower_bound(segment.begin(),segment.end(),tp);
tp1 = it - segment.begin() ;
//deb("rd",tp,tp1);
if(tp1 == n)
return n+1 ;

if(segment[tp1] == tp and tp1 and tp != 1000000000)
{
tp1++;

mx1 = max(mx1,tp1+1);

if(mn == -1 or tp1<mn)
mn = tp1 ;
}

else
{
tp1++;

if(mx2 != -1 and mx2 != tp1)
ok = 1 ;

mx2 = max(mx2,tp1);
}
}
//deb("red",mx1,mn,mx2);
if(ok or mx1-mn > 2)
{
mx2 = max(mx2,mx1);
return mx2 ;
}

else
{
if(mx2 == -1)
{
if(mx1 - mn == 2)
{
rd.fs = mn+1 ;
return mn+1 ;
}

else
{
rd.fs = mx1 ;
rd.sc = mn ;
return mx1 ;
}
}

else
{
if(mx1-mn == 2)
{
if(mn+1 == mx2)
{
rd.fs = mx2 ;
return mx2 ;
}

else
return max(mx2,mx1);
}

else
{
if(mx1 == mx2 or mx2 == mn)
{
rd.fs = mx2 ;
return mx2 ;
}

else
{
if(mx1 == mn)
rd.fs = mx2 ;

return max(mx2,mx1);
}
}
}
}
}

ll cal_green(ll tme)
{
ll tp , tp1 , mx = n+2 , mn1 = n+2 , mn2 = n+2 , temp = 0 ;
bool ok = 0 ;

gr = mp(-1,-1);

for(int i=0 ; i<g ; i++)
{
tp = green[i].fs - green[i].sc*tme ;

if(tp<0)
return 0 ;
//deb("gr",tp);
it = lower_bound(segment.begin(),segment.end(),tp);
tp1 = it - segment.begin();
//deb(tp1);
if(tp1 == n)
{
mn2 = min(mn2,n+1);
continue;
}

if(segment[tp1] == tp and tp1 and tp != 1000000000)
{
tp1++;

mn1 = min(mn1,tp1);

if(mx == n+2 or tp1+1>mx)
mx = tp1 + 1;

temp = mx - mn1 ;
}

else
{
tp1++;

if(mn2 != n+2 and mn2 != tp1)
ok = 1 ;

mn2 = min(mn2,tp1);
}
}
//deb("green",mn1,mx,mn2);
if(ok or temp>2)
{
mn2 = min(mn2,mn1);
return mn2 ;
}

else
{
if(mn2 == n+2)
{
if(temp == 2)
{
gr.fs = mn1 + 1;
return mn1+1 ;
}

else
{
gr.fs = mn1 ;
gr.sc = mx ;

return mn1 ;
}
}

else
{
if(temp == 2)
{
if(mn1+1 == mn2)
{
gr.fs = mn2 ;
return mn2 ;
}

else
return min(mn2,mn1);
}

else
{
if(mn2 == mn1 or mn2 == mx)
{
gr.fs = mn2 ;
return mn2 ;
}

else
{
if(mn1 == mx)
gr.fs = mn2 ;

return min(mn2,mn1);
}
}
}
}
}

ll b_search()
{
ll l = 0 , r = 1000000010 , mid ;
ll lmn = 0 , rmn = r ;

while(l<=r)
{
mid = (l+r)/2LL ;
//deb(l,r,mid);
if(cal_red(mid)<cal_green(mid))
l = mid + 1 ;

else
{
if(rd.fs != -1)
{
if(rd.fs == gr.fs)
rmn = min(rmn,mid) ;

else if(rd.fs == gr.sc)
rmn = min(rmn,mid) ;
}

if(rd.sc != -1)
{
if(rd.sc == gr.fs)
rmn = min(mid,rmn) ;

else if(rd.sc == gr.sc)
rmn = min(mid,rmn) ;
}

r = mid - 1 ;
}
}

//    if(rmn == 1000000010)
//        return -1 ;

for(ll i=max(r-1,0LL) ; i<=l+1 ; i++)
{
cal_green(i);
cal_red(i) ;

if(rd.fs != -1)
{
if(rd.fs == gr.fs)
return i ;

else if(rd.fs == gr.sc)
return i ;
}

if(rd.sc != -1)
{
if(rd.sc == gr.fs)
return i ;

else if(rd.sc == gr.sc)
return i ;
}
}

return -1 ;
}

int main()
{
int tcase ;
ll tp , tp1 , tp2 ;

sf1(tcase);

foren(cas,1,tcase)
{
sf2ll(r,g);
sf1ll(n);

segment.clear();

for(int i=0 ; i<r ; i++)
sf1ll(red[i].fs);

for(int i=0 ; i<r ; i++)
sf1ll(red[i].sc);

for(int i=0 ; i<g ; i++)
sf1ll(green[i].fs);

for(int i=0 ; i<g ; i++)
sf1ll(green[i].sc);

for(int i=0 ; i<n ; i++)
{
sf1ll(tp);
segment.pb(tp);
}

segment.pb(0);
segment.pb(1000000000);

n+=2 ;

sort(segment.begin(),segment.end());
//deb(cal_red(0),cal_green(0));wait;
ll ans = b_search();

pf("Case %d: %lld\n",cas,ans);

}

return 0 ;
}

/*

2
1 1 1
10
10000
20
10000
1000000
2 2 1
1 2
99 100
1000 1001
100 200
100

1
1 1 10
0
1
1000000000
0
10 100 200 350 460 70 900 1000 3000 999999999

1
1 1 11
10
1
14
1
10 100 200 350 460 70 900 1000 3000 999999999 12

1
2 2 12
1 0
999999998 999999999
1000000000 0
1 1000000
10 100 200 350 460 70 900 1000 3000 999999999 12 500000000

*/

``````