13001 - Jumping Frogs

[brianfry713]

Use this thread to discuss this problem.

[draak_krijger]

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

please help me ....., please ....

mycode :

Code: Select all

// Pre_code

#include <bits/stdc++.h>

// header file

#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

#pragma comment(linker, "/STACK:667772160")
#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 Read freopen("C:\\Users\\RONIN-47\\Desktop\\input_output\\input.txt","r",stdin)
#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()
{
    //Read;
    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



*/