Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | Страница 2 | 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:) | 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 | HELP!!! TLE in #9 | garnett | 1156. Два тура | 10 ноя 2013 13:16 | 1 | | 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; } | 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 | .. | 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. | 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! | 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... | wa3 | Egor Stepanov [mikroz] | 1156. Два тура | 18 апр 2008 18:40 | 1 | wa3 Egor Stepanov [mikroz] 18 апр 2008 18:40 Please help me! I can't understand why I got WA on third test... Edited by author 31.05.2008 03:32 | WA Test #3 | JC7 | 1156. Два тура | 18 мар 2008 21:01 | 1 | | I'm just crazy about Test#3, can someone help me find my bug? | EarthShaker | 1156. Два тура | 10 мар 2008 13:52 | 2 | This is my Code: [code deleted] Thanks A Lot!!! Edited by moderator 11.03.2008 13:24 I have found my bug and got AC. This test helped me: Input 6 9 1 2 1 3 1 4 5 6 5 7 5 8 9 10 9 11 9 12 Output IMPOSSIBLE | I don't kown why I got WA in test 3# !!! I have try lots of test! please help!! | alvin | 1156. Два тура | 17 сен 2007 07:58 | 1 | | Страница 1 | statement of problem is not logistical | Alias (Alexander Prudaev) | 1156. Два тура | 25 авг 2007 17:03 | 1 | i write program which have wa#1 "But it appeared that among those problems there were some, which have the analogous solutions." for me it's very difficult to understand such situation: solution of problem A is "analogous" to solution of problem B and solution of problem B is "analogous" to solution of problem C BUT solution of problem A is NOT "analogous" to solution of problem C in other words relation "analogous" is not transitive this fact must be clarified in the problem statement | 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 | 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 |
|
|