Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | WA 7 test | Конобейцев Иван Олегович | 1156. Два тура | 24 сен 2022 19:49 | 1 | WA 7 test Конобейцев Иван Олегович 24 сен 2022 19:49 | If you have WA or TLE on #8 | Amon | 1156. Два тура | 12 авг 2021 16:40 | 1 | Try 7 10 1 2 1 3 1 4 5 6 5 7 8 9 8 10 8 11 12 13 12 14 This test changed my solution totally. Hope it helps you:) | if you get wa, try this test, maybe will help you | Huang WenHao | 1156. Два тура | 18 май 2021 17:40 | 4 | Test: 6 5 1 2 4 3 2 9 2 4 4 1 Ans: IMPOSSIBLE Thank you very mutch!!! It's very helpfull if somebody get WA7. (We just cann't paint this graph on 2 colors. ) A very good test, thanks. I had WA7 and now I have AC, using this one | TEST | buyolitsez | 1156. Два тура | 3 сен 2019 09:22 | 1 | TEST buyolitsez 3 сен 2019 09:22 3 4 1 2 1 3 4 5 4 6 ans: 1 5 6 2 3 4 Edited by author 03.09.2019 09:23 | WA 3 too... | Combatcook | 1156. Два тура | 26 июл 2016 16:17 | 3 | Many people has already written about it, but... I really don't understand why I get WA. My program pass all tests here. Please, help to find bug. -- Edited by author 29.07.2016 15:52 Contact me and maybe i'll have some suggestions to help you out~ Edited by author 26.07.2016 17:05 | ADMINS: WEAK TEST CASES | GastonFontenla | 1156. Два тура | 12 июн 2016 13:51 | 2 | Hi! My code has complexity O(2^N) and it had AC in 0.001 sec. A friend of mine noted this: when I run my program in this case: 50 50 1 2 3 4 5 6 ... Same pattern here 95 96 97 98 99 100 And it will give TLE. Please, add this case! 50 50 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 | If you have WA9...(+) | Dart MirzMan C++ Edition (Mirzoyan Alexey, Rybinsk SAAT) | 1156. Два тура | 14 окт 2015 11:04 | 6 | Try this test: 2 1 1 3 answer: 2 3 1 4 I have wa#9,but my program does well in your data The case given here helped me. Notice that when you are selecting whether white part is to be selected or black part, and pushing the result in a vector or queue, due to DP, last part gets inserted first. So you have to consider that first result in the vector/queue is for the last pair of partition. May be this will help... 2 4 1 2 2 1 1 2 2 1 answer: 1 3 2 4 answer 1 2 3 4 is correct too. But I have wa3 | Test7 is correct??? | Korotkevich Piotr | 1156. Два тура | 19 июл 2014 15:43 | 2 | Help me. I got WA7. Give me some test. I was failing this test because I printed stuff after IMPOSSIBLE (restoring solution even though I found there shouldn't be one). | HELP!!! TLE in #9 | garnett | 1156. Два тура | 10 ноя 2013 13:16 | 1 | | I use Dynamic Prog. May Be It's wrong. Help with test or hint, please. WA#3 | Alexey | 1156. Два тура | 25 сен 2013 23:00 | 7 | My programm passes all my tests, but WA#3. Please, help. Thanks a lot. How you here have applied Dinamic Prog.? I the ambassador aside graph. Hi, Taras. I use simple method: I read two variables ot and ku. If ot and ku are in the same group, I Output('IMPOSSIBLE'); If they are in the different groups then I Continue else I put one variable into the first group and other into the second group. After that I divide "free" tasks between the groups... I hoped that It would get more than two tests... May be I should try to use graphs... BTW, tell me youre ICQ number, I cann't find you... Edited by author 02.05.2006 13:17 try this test, maybe will help you: 4 6 1 2 2 3 3 4 4 5 6 7 7 8 ANS: 1 3 5 7 2 4 6 8 You can use it. I used it as well. First you must paint the graph with black and white (use BFS) so that two vertices with the same edge are of different colors. After that you have pairs of integers and you have to combine them so that you have N in each round (that's not always possible). how I should combine them ?? | chorti amocanaa | Avtandil Goqadze | 1156. Два тура | 25 июн 2013 03:14 | 2 | | WA#3 again... | pasha | 1156. Два тура | 22 мар 2013 18:32 | 1 | I've tested all inputs from other themes, but still got wa in 3rd. Help, please! The algorithm based on the half-invariant idea. #include <iostream> #include <fstream> #include <string> #include <math.h> #include <sstream> using namespace std; int main(){ int n, m; cin >> n >> m; bool **e = new bool*[2*n]; for (int i=0; i<2*n; i++){ e[i] = new bool[2*n]; for (int j=0; j<2*n; j++){ e[i][j] = false; } } int v1, v2; for (int i=0; i<m; i++){ cin >> v1 >> v2; int tmp; if (v1 > v2){ tmp = v1; v1 = v2; v2 = tmp; } e[v1-1][v2-1] = true; e[v2-1][v1-1] = true; } int inv=0; for (int i=0; i<n; i++){ for (int j=i+1; j<n; j++){ if (e[i][j]) inv++; if (e[n+i][n+j]) inv++; } } int *t =new int[2*n]; for (int i=0; i<2*n; i++){ t[i] = i; } while (inv > 0){ int s = 0; for (int i=0; i<n; i++){ int i_out = 0; int i_in = 0; for (int k=0; k<n; k++){ if (e[t[i]][t[k]] || e[t[k]][t[i]]){ i_in++; } if (e[t[i]][t[k+n]] || e[t[k+n]][t[i]]){ i_out++; } } for (int j=n; j<2*n; j++){ int j_out = 0; int j_in = 0; for (int k=0; k<n; k++){ if (e[t[k+n]][t[j]] || e[t[j]][t[k+n]]){ j_in++; } if (e[t[k]][t[j]] || e[t[j]][t[k]]){ j_out++; } } if (e[t[i]][t[j]] || e[t[j]][t[i]]){ j_out--; j_out--; } if (i_in + j_in > i_out + j_out){ s++; inv -= (i_in + j_in - i_out - j_out); int tmp = t[i]; t[i] = t[j]; t[j] = tmp; } if (s == 1) break; } if (s == 1) break; } if (s == 0){ cout << "IMPOSSIBLE\n"; return 0; } } string tour1, tour2; tour1 = ""; tour2 = ""; for (int i=0; i<n; i++){ for (int j=i+1; j<n; j++){ if (t[i]>t[j]){ int tmp = t[i]; t[i] = t[j]; t[j] = tmp; } if (t[i+n]>t[j+n]){ int tmp = t[i+n]; t[i+n] = t[j+n]; t[j+n] = tmp; } } } for (int i=0; i<n; i++){ std::ostringstream ostr; ostr << (t[i]+1); std::string theNumberString = ostr.str(); tour1 = tour1 + theNumberString + " "; } for (int i=0; i<n; i++){ std::ostringstream ostr; ostr << (t[n+i]+1); std::string theNumberString = ostr.str(); tour2 = tour2 + theNumberString + " "; } cout << tour1 << endl << tour2 << endl; return 0; } | Whats wrong.Help with test 8!! | Серовиков Андрей | 1156. Два тура | 8 июл 2012 18:21 | 3 | I had WA#8 and miraculously found a bug in my backtracking&memorization with the following test: > 50 2 > 99 100 > 98 99 The problem was in printing a solution, when N tasks for the first round are prepared properly, but the other N are contradictory (because I quit from backtracking too soon). We probably wouldn't have experienced this if we had written a proper DP solution instead. :-) Edited by author 08.07.2012 18:21 | .. | KALO | 1156. Два тура | 17 сен 2011 22:33 | 2 | .. KALO 12 фев 2010 20:30 if you use brute search and got TLE then try to sort the input. :-D Re: .. Azat Yusupov(TUIT Urgench) 17 сен 2011 22:33 Thank you very much! I got accepted after sorting pairs with their sum. | WA3. Plz Help Me. | Programmer | 1156. Два тура | 25 сен 2010 20:44 | 5 | This test help me. 7 10 1 2 1 3 1 4 5 6 5 7 8 9 8 10 8 11 12 13 12 14 Edited by author 04.02.2009 17:56 Thanks! It really helped me a lot on WA7! Actually, it was because I used an array color[100], but I forgot to set them to -1! It would be very hard to find that out without your help... | WA #3. Take pity! Give me this test... | ashim | 1156. Два тура | 17 сен 2010 02:29 | 1 | I tried all tests given here (also in other forum messages) and always get correct answer. I have no idea, what's wrong with this: #include <iostream> #include <cmath> using namespace std; class Task { public: int arrSameTasks[101], lastIndex; bool IsInTour; Task() { IsInTour = false; lastIndex = 0; }
void AddSameTask(int someTask) { lastIndex++; arrSameTasks[lastIndex] = someTask; } void Show() { for (int i = 1; i <= lastIndex; i++) cout << arrSameTasks[i] << " "; cout << endl; } bool SameTasksFounded(int arrToCheck[], int n) { for (int i = 1; i <= lastIndex; i++) { for (int j = 1; j <= n; j++) { if (arrSameTasks[i] == arrToCheck[j]) return true; } } return false; } }; class TempTours // промежуточные расположения задач в турах { public: TempTours() {} int tempTour1[101], tempTour2[101], tempIndex1, tempIndex2; void CreateData(int tour1[], int tour2[], int index1, int index2) { for (int i = 1; i <= index1; i++) tempTour1[i] = tour1[i]; for (int i = 1; i <= index2; i++) tempTour2[i] = tour2[i]; tempIndex1 = index1; tempIndex2 = index2; } int IndDifference() { return abs (tempIndex1 - tempIndex2); } void Show() { cout << "\ntempTour1:\n"; for (int i = 1; i <= tempIndex1; i++) cout << tempTour1[i] << " "; cout << "\ntempTour2:\n"; for (int i = 1; i <= tempIndex2; i++) cout << tempTour2[i] << " "; } }; bool MakeArrays(Task allTasks[], int n, int tour1[], int tour2[], int &index1, int &index2, int freeTasks[], int &indexFree) { bool ListsChanged; // будем проверять, сделаны ли изменения в списках туров for (;;) { indexFree = 1; ListsChanged = false; for (int i = 1; i <= 2*n; i++) { if (!(allTasks[i].IsInTour)) // поиск первой свободной задачи { if (!(allTasks[i].SameTasksFounded(tour1, index1))) // если в 1-ом туре не найдено подобных задач,... { // ...а во 2-ом туре такие есть или число задач в командах сейчас равно if (allTasks[i].SameTasksFounded(tour2, index2) || index1 == index2) { if (index1 > n) // а тут мы превысили число задач в одном туре { cout << "IMPOSSIBLE"; return false; } tour1[index1] = i; index1++; allTasks[i].IsInTour = true; // помещаем ее в 1-ый тур ListsChanged = true; } else // а если нет "врагов" ни там, ни там + индексы не равны { freeTasks[indexFree] = i; indexFree++; } } else // если в 1-ом туре есть подобные задачи,... { if (!(allTasks[i].SameTasksFounded(tour2, index2))) // ...а во 2-ом их нету { if (index2 > n) // тут мы опять превысили число задач в одном туре { cout << "IMPOSSIBLE"; return false; } tour2[index2] = i; index2++; allTasks[i].IsInTour = true; // помещаем ее во 2-ой тур ListsChanged = true; } else // а если "враги" повсюду { cout << "IMPOSSIBLE"; return false; } } } } if (!ListsChanged) // наконец, когда списки перестали меняться return true; } } int Max(int arr[], int n) { int max = arr[0], maxIndex = 0; for (int i = 1; i < n; i++) if (arr[i] > max) { max = arr[i]; maxIndex = i; } return maxIndex; } int main() { freopen("input.txt", "r", stdin); int n, m; cin >> n >> m; Task * allTasks = new Task[2*n+1]; // массив всех задач int task1, task2; for (int i = 1; i <= m; i++) { cin >> task1 >> task2; allTasks[task1].AddSameTask(task2); allTasks[task2].AddSameTask(task1); } /*for (int i = 1; i <= 2*n; i++) { cout << "Same tasks for task " << i << ": \n"; allTasks[i].Show(); }*/
int tour1[51], tour2[51]; // задачи 1-ого тура, задачи 2-ого тура int index1 = 1, index2 = 1; // индексы, указывающие, куда вставлять очередную задачу int freeTasks[101], indexFree = 1; // здесь будут храниться временно незанятые задачи, у которых на момент проверки не будет "врагов" ни в одном туре TempTours * arrTempTours = new TempTours[2*n+1]; int indexTemp = 0; // Проход по всем задачам и генерация временных пар массивов задач for (;;) { indexFree = 1; index1 = 1; index2 = 1; if (!MakeArrays(allTasks, n, tour1, tour2, index1, index2, freeTasks, indexFree)) return 0; index1--; index2--; arrTempTours[indexTemp].CreateData(tour1, tour2, index1, index2);
//cout << "\narrTempTours[" << indexTemp << "]:"; //arrTempTours[indexTemp].Show(); indexTemp++; if (indexFree == 1) break; } indexFree = 1; index1 = 1; index2 = 1; int * arrDiff = new int[2*n+1]; for (int i = 0; i < indexTemp; i++) arrDiff[i] = arrTempTours[i].IndDifference(); for (int i = 0; i < indexTemp; i++) { int tempInd1 = arrTempTours[Max(arrDiff, indexTemp)].tempIndex1; int tempInd2 = arrTempTours[Max(arrDiff, indexTemp)].tempIndex2; if (index1 == index2) { for (int j = index1; j < index1 + tempInd1; j++) tour1[j] = arrTempTours[Max(arrDiff, indexTemp)].tempTour1[j-index1+1]; index1 += tempInd1; for (int j = index2; j < index2 + tempInd2; j++) tour2[j] = arrTempTours[Max(arrDiff, indexTemp)].tempTour2[j-index2+1]; index2 += tempInd2; } else { if (index1 < index2) { if (tempInd1 > tempInd2) { for (int j = index1; j < index1 + tempInd1; j++) tour1[j] = arrTempTours[Max(arrDiff, indexTemp)].tempTour1[j-index1+1]; index1 += tempInd1; for (int j = index2; j < index2 + tempInd2; j++) tour2[j] = arrTempTours[Max(arrDiff, indexTemp)].tempTour2[j-index2+1]; index2 += tempInd2; } else { for (int j = index1; j < index1 + tempInd2; j++) tour1[j] = arrTempTours[Max(arrDiff, indexTemp)].tempTour2[j-index1+1]; index1 += tempInd2; for (int j = index2; j < index2 + tempInd1; j++) tour2[j] = arrTempTours[Max(arrDiff, indexTemp)].tempTour1[j-index2+1]; index2 += tempInd1; } } else { if (tempInd1 < tempInd2) { for (int j = index1; j < index1 + tempInd1; j++) tour1[j] = arrTempTours[Max(arrDiff, indexTemp)].tempTour1[j-index1+1]; index1 += tempInd1; for (int j = index2; j < index2 + tempInd2; j++) tour2[j] = arrTempTours[Max(arrDiff, indexTemp)].tempTour2[j-index2+1]; index2 += tempInd2; } else { for (int j = index1; j < index1 + tempInd2; j++) tour1[j] = arrTempTours[Max(arrDiff, indexTemp)].tempTour2[j-index1+1]; index1 += tempInd2; for (int j = index2; j < index2 + tempInd1; j++) tour2[j] = arrTempTours[Max(arrDiff, indexTemp)].tempTour1[j-index2+1]; index2 += tempInd1; } } } if (index1-1 > n || index2-1 > n) // переполнение числа задач в одном туре { cout << "IMPOSSIBLE"; return 0; } arrDiff[Max(arrDiff, indexTemp)] = -1; } for (int i = 1; i <= n; i++) cout << tour1[i] << " "; cout << "\n"; for (int i = 1; i <= n; i++) cout << tour2[i] << " ";
return 0; } I've been trying to get AC with this program for 2 days and... yes, it's rather big. Somebody, if you've got a heart, please give me test #3! )) Edited by author 17.09.2010 02:31 | help!WA#2 | sokoL[TSOGU™] | 1156. Два тура | 4 дек 2009 23:45 | 1 | #include<stdio.h> #include<iostream> using namespace std; int a,b,n,m,g[1000][1000]; int _max = -1000; int main() { scanf("%d %d",&n,&m); for(int i = 1;i<=m;i++) { scanf("%d %d",&a,&b); g[a][b]=1; g[b][a]=1; } for(int k = 1;k<=2*n;k++) { for(int l = 1;l<=2*n;l++) { if(k==l){continue;} else if(g[k][l]==1) { g[k][l]=2; g[k][l]=2; } } } for(int k = 1;k<=2*n;k++) { for(int l = 1;l<=2*n;l++) { if(k==l){continue;} else if(g[k][l]==0) { g[k][l]=1; g[k][l]=1; } } } int key = 0; for(int k = 1;k<=2*n;k++) { for(int l = 1;l<=2*n;l++) { if(key>=2){return 0;} else if(k==l){continue;} else if(g[k][l]==1) { printf("%d %d\n",k,l); key++; } } } printf("IMPOSSIBLE"); } | Anybody know why wa4? | tiancaihb | 1156. Два тура | 18 сен 2009 15:11 | 2 | Very strange... I tried all tests here and they all worked well. It's a DP,right? But I always get wa4. I added this to my code: when I worked out my answer, I'll check them myself. If there are some shouldn't be in the same pair,then while(1). As a result I got TLE4. So it obviously I've made a wrong answer. BUT HOW COULD IT HAPPEN!!! Well, it was because of my wrong algo. And I've got WA7 later, that's because I misspelled IMPOSSIBLE in dfs. (There were two of this word in my prog, one is in dfs and the other is after DP) It took me an hour to debug for this! Whoa-a! | WA#3 | @ntiFreeze | 1156. Два тура | 4 янв 2009 18:56 | 8 | WA#3 @ntiFreeze 25 фев 2007 14:34 it seems that my program has no bug. it pass all test on board and all my tests. I bicolored graph. then used DP to find answer but I got WA3. *** I have found mistake. AC now! this test helped me very much: 50 2 99 100 98 99 Edited by author 25.02.2007 19:13 This test is really helpful to me. Thx a lot. ((( my DP get WA3 but brute force get AC There is no testdata like this! I didn't Consider it and ACed now. So I think the problem number is in [1,2n] For all those who got WA#3 with dfs and DP, The case given here didn't help me but 2 1 1 3 helped me. Notice that when you are selecting whether white part is to be selected or black part, and pushing the result in a vector or queue, due to DP, last part gets inserted first. So you have to consider that first result in the vector/queue is for the last pair of partition. May be this will help... Edited by author 04.01.2009 19:08 Edited by author 04.01.2009 19:08 | for the one who got WA | Gnocuil | 1156. Два тура | 8 ноя 2008 15:33 | 2 | If you think your algorithm is correct and still got WA , try to use adj-matrix,don't use adj-list I use adj-matrix but I still got WA |
|
|