ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1773. Metro to Every Home

I HAVE ONLY WA16! PLEASE, WHAT IS WRONG?
Posted by xurshid_n 17 Oct 2011 14:03
there source code

int main()
{

if ( solve() == true)
{
normal();
write();
}
else
{
printf("0\n");
}

return ( 0 );
}

#define HIGHT_NUMBER 100001

#define NUMBER 50005

//// sizeof(a) = 5*10^4 * sizeof(int) = 20*10^4 = 2*10^5 = 0.2 Mbyte
static int a[NUMBER]; //left hight

//sizeof(b) = 0.2 Mbyte
static int b[NUMBER];//right hight

//sizeof(ha) = 0.2 Mbyte
static int ha[NUMBER];// hight - a[i]

//sizeof(hb) = 0.2 Mbyte
static int hb[NUMBER];// hight - b[i]

//sizeof(used) = 0.2 Mbyte
static Bool_T used[NUMBER];// used[i] = true, if self, used[i] = false, if rotate used

//sizeof(res) = 0.2 Mbyte
static int res[NUMBER];// result indexes

//sizeof(r1) = 10^5 * 4 = 0.4 Mbyte
static int r1[HIGHT_NUMBER];//temporary array

//sizeof(r2) = 0.4 Mbyte
static int r2[HIGHT_NUMBER];//temporary array

/////total : 0.2 * 6 + 0.4*2 = 1.2 + 0.8 = 2 Mbyte;

static int number; // number of glass
static int hight;    // hight of glass

static int difference;
static int absDifference;
static int remainder;

{
int i;

scanf("%d %d", &hight, &number );

for ( i = 1; i <= number; i++)
{
scanf("%d%d",&a[i],&b[i]);

ha[i] = hight - a[i];
hb[i] = hight - b[i];
}
}

void write()
{
int i;
for(i = 1; i< number;i++)
{
printf("%d ", res[i]);
}
printf("%d\n",res[number]);
}

static
Bool_T checkRes()
{
int i;
for( i = 1; i <= number - 1; i++)
{
if (a[ res[ i + 1 ] ] !=  b[ res[ i ] ] )
return false;
}
return true;
}

void normal()
{
int i ;
for ( i = 1; i <= number; i++ )
{
if (  used[ res[ i ] ] == false )
res[ i ] = - res[ i ];
}
}

static
int pushUp()
{
int i;
int rn = 0;
for( i = 0; i <= hight; i++)
{
if ( r1[ i ] > 0)
{
res[++rn] = r1[i];
}
}
return rn;
}

static
int pushDown()
{
int i;
int rn = 0 ;
for(i = hight; i>= 0; i--)
{
if (r1[i] > 0)
{
res[++rn] = r1[i];
}
}

return rn;
}

static
int push()
{
return (difference < 0) ? pushUp(): pushDown();
}

static
Bool_T horizontal()
{
int i;
const int  h = a[ 1 ] ;

if ( ! ( difference == 0 ) )
{
return false;
}

for(i = 1; i <= number; i++)
{
if (a[i] != b[i])
return false;

if ( ( a[i] != h ) &&  (  hb[i] != h ))
{
return false;
}
res[ i ] = i;
used[i]  = ( ( a[ i ] == h ) ? true : false);
if ( ! used[i] )
{
a[i] = hb[i];
b[i] = ha[i];
}
}

return true;
}

static
Bool_T Difficult()
{
int i, t;
int rn;

//check to changeable
//if ( !IsDifficult()  )
//{
//    return false;
//}

for(i = 1; i <= number;i++)
{
used[i] = true;
}

for(i = 0; i<= hight; i++)
r1[i] = r2[i] = 0;

for(i = 1 ; i<= number;i++)
{
if (r1[a[i]] == 0)
{
r1[a[i]] = i;
}
else if ( r2[ a[ i ] ] == 0 )
{
r2[a[i]] = i;
}
else
{
return false;
}
}

for(i = 0; i<= hight;i++)
{
if ( r1[ i ] > 0 && r2[ i ] > 0 )
{
int r2i = r2[ i ];

if( r1[ hb[ r2i ] ] > 0 )
{
return false;
}

r1[ hb[ r2i ] ] = r2i;

used[ r2i ] = false ;

a[r2i] = hb[r2i];
b[r2i] = ha[r2i];
}
}

rn = push();

if (rn != number)
{
return false;
}

return checkRes();
}
static
Bool_T DifCheck()
{
int i;
for( i = 1; i<= number ; i++)
{
if ( a[i] - b[i] != difference )
{
return false ;
}
}

return true;
}

Bool_T solve()
{
difference = a[1] - b[1] ;
absDifference = abs(difference);
remainder = ( absDifference == 0) ? 0 : (a[1] % absDifference ) ;
if ( DifCheck() )
if (difference == 0)
return horizontal();
else
return Difficult();

else
return false;
}