|
|
Can anybody give me ideas about 21 test, please? Edited by author 18.10.2020 22:11 Edited by author 19.10.2020 03:42 Dear anyone, show me the 11th test case please! why? I have passed through it by changing the place where I considered that a particular stripe has been already rotated. I have no idea why it was wrong though. I got WA 27, and I found that my program could not pass the following test: 7 2 6 4 5 3 The correct answer should be 1 -2 or 2 -1, but my incorrect program output 0. I fixed it and got AC. 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; } give me test please Try test: 2 2 0 0 2 2 ans: 1 -2 on russian : Перед наклеиванием на стену полосы можно переворачивать. просто согласно вашим условиям на первый тест корректным будет ответ : -2 -1 -3. Но я получаю WA#1. right : Перед наклеиванием на стену полосы можно поворачивать. Тогда тогда ответ -2 -1 -3 неверен, а ваш тест верен. -3 1 2 and -2 -1 3 are right, but not -2 -1 -3. Why -2 -1 -3 should be correct? Segments on the 1st and 3rd strips don't form straight line in it. Хорошо, но как вы думаете, какая разница между поворачивать и переворачивать? Я думаю, что переворачивать - означает, возможность перевернуть лист на другую сторону! а согласно вашим тестам, корректнее употребить поворачивать - возможность вращать лист вокруг оси. oops! sorry, for first test answer -2 -1 -3 - incorrect, but said me please, what answer for this test : 3 2 2 1 0 1 Answer is 0. P.S. I changed "переворачивать" to "переворачивать вверх ногами" in the statement. Edited by author 22.08.2010 15:16 Думаю картинка показывающая как следует переворачивать/поворачивать и т.п. показывает что именно надо сделать :))) good luck... Does anybody gain it? Your ideas? Well, my fault, didn't read statement carefully. |
|
|