1 / 4
Jan 2015

Code : ideone.com/vDKBX0

#include<iostream>
#include<algorithm>
#include<vector>
#include<stdio.h>
using namespace std;
class times
{
    public:
    int h,m,s,ms;
    int mili;
    times ()
{
    h = m=s=ms =0;
    mili = 0;
}


times(int a,int b,int c,int d)
{
    h = a,m=b,s=c,ms=d;
    make();
}
   void bake( ) //do reverse of make() for given mili
   {
        long int x = mili;
        ms = x%1000;
        x /= 1000;
        s = x%60;
        x/= 60;
        m = x%60;
        x /= 60;
   }
   void make()  // calc total mili based on cur val of h,m,s and ms
   {
        mili = ms;
        mili += s*1000 + m*60*1000 + h*3600*1000;
   }
};
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
   int h,m,s,msl;
   bool flag;
   string str;
        scanf("%d:%d:%d:%d",&h,&m,&s,&msl);
        times mid(h,m,s,msl);
    int low=0,high;

    high = mid.mili;
    while( low < high )
    {
        mid.mili = (high+low)/2;


        mid.bake();


       printf("%d:%02d:%02d:%03d" , mid.h , mid.m,mid.s,mid.ms );
        fflush(stdout); //FLUSH

        cin>>str; // the relic

        if(str=="PLATINUM") // we have more time than req
            {
                low = mid.mili+1;
                //low.bake();
                flag = true;
            }
        else
            {
                high = mid.mili-1;
               // high.bake();
                flag = false;
            }

           // break;

    }
    if(!flag)
    {
       // mid.mili -= 1;
        //mid.bake();
        mid.mili = high;
        mid.bake();
    printf("PLATINUM: %d:%02d:%02d:%03d" ,mid.h , mid.m,mid.s,mid.ms);
    }
    else
    {

       mid.mili = low;
        mid.bake();
    printf("PLATINUM: %d:%02d:%02d:%03d" ,mid.h , mid.m,mid.s,mid.ms);


    }






return 0;
}

Logic : Binary Search

if "PLATINUM" low = mid+1
else high = mid - 1

I m getting TLE , i just don't understand how, any hints as to what optimizations i need to do? , given than all those who solved this have done so in 0.00 , gives me a clue that there is a better algo , is this true? , better than O(log n) ?

Does using a string with cin , along with scanf and printf causing this?

Any hints ?

  • created

    Jan '15
  • last reply

    Jan '15
  • 3

    replies

  • 365

    views

  • 2

    users

  • 1

    link

Using cin and scanf together causes no issues unless you set sync_with_stdio to false.

thanks, but that did'nt fixed TLE yet.

Can you give hint , as how to improve the algo?

I would be worried about this one.