Page 2 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:) 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 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 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 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; } 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 if you use brute search and got TLE then try to sort the input. :-D Thank you very much! I got accepted after sorting pairs with their sum. #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"); } 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! What test is it? 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... Please help me! I can't understand why I got WA on third test... Edited by author 31.05.2008 03:32 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 Page 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 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 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 |
|