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 ?
