|
|
вернуться в форумI HAVE ONLY WA16! PLEASE, WHAT IS WRONG? there source code int main() {
read();
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; void read() { 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; } |
|
|