What's Test 9? I saw, that Test 9: 7 1 3 2 5 2 5 4 7 6 9 6 9 8 10 My answer: 3 1 3 4 7 8 10 What's correct answer? My program runs any tests from other topics perfectly, but something is wrong with the task 1. Sounds like madness. Edited by author 24.02.2022 23:04 Edited by author 24.02.2022 23:05 I got WA in first test. I checked my program using a lot of compiler and in first test my program outputs is correct. my code id:9308865 Hello. My program passes all tests from the forum, but I still get WA6. I do brute force First, I go through all the elements that are to the right of the current one, then everything that is to the left can anyone have any tests? here is y code is needed: #include <iostream> using namespace std; int n, result = 0, sizeHelpArray = 0, sizeAnswerArray; int line[100][2], helpArray[100][2], answerArray[100][2]; //initialization and sorting on the left border void Init() { int i, j; cin >> n; for (i = 0; i < n; i++) { cin >> line[i][0] >> line[i][1]; if (line[i][0] > line[i][1]) swap(line[i][0], line[i][1]); } for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { if (line[j][0] < line[i][0]) { swap(line[i][0], line[j][0]); swap(line[i][1], line[j][1]); } if(line[j][0] == line[i][0]) if (line[j][1] < line[i][1]) { swap(line[i][0], line[j][0]); swap(line[i][1], line[j][1]); } } } } //adding a segment to the temporary answer void AddInHelpArray(int index) { sizeHelpArray++; helpArray[sizeHelpArray][0] = line[index][0]; helpArray[sizeHelpArray][1] = line[index][1]; } //to record the best current result void copyInAnswerArray() { int i; for (i = 0; i < sizeHelpArray + 1; i++) { answerArray[i][0] = helpArray[i][0]; answerArray[i][1] = helpArray[i][1]; } } void sortAnswerArray() { for (int i = 0; i <= sizeAnswerArray; i++) { for (int j = i + 1; j <= sizeAnswerArray; j++) { if (answerArray[j][0] < answerArray[i][0]) { swap(answerArray[i][0], answerArray[j][0]); swap(answerArray[i][1], answerArray[j][1]); } if (answerArray[j][0] == answerArray[i][0]) if (answerArray[j][1] < answerArray[i][1]) { swap(answerArray[i][0], answerArray[j][0]); swap(answerArray[i][1], answerArray[j][1]); } } } } void Solve() { int i, x, tmp = 1, currentPoint; //starting from the first element .. for (x = 0; x < n; x++) { sizeHelpArray = 0; tmp = 1; memset(helpArray, 0, sizeof(helpArray)); //I write the current element to an auxiliary array helpArray[sizeHelpArray][0] = line[x][0]; helpArray[sizeHelpArray][1] = line[x][1]; currentPoint = line[x][1]; //Checking items to the right of the current one for (i = x + 1; i < n; i++) { if (line[i][0] >= currentPoint) { tmp++; currentPoint = line[i][1]; AddInHelpArray(i); } }
currentPoint = line[x][0]; int border; border = line[x][0]; bool first = true; //Checking items to the left of the current one for (int j = 0; j < x; j++) { if (line[j][1] <= currentPoint && first) { tmp++; currentPoint = line[j][1]; AddInHelpArray(j); first = false; } else if (first == false && line[j][0] >= currentPoint && line[j][1] <= border) { tmp++; currentPoint = line[j][1]; AddInHelpArray(j); } } //If the result is better than the previous one, then I save it. if (tmp > result) { result = tmp; copyInAnswerArray(); sizeAnswerArray = sizeHelpArray; } } sortAnswerArray(); cout << result << endl; for (int i = 0; i <= sizeAnswerArray; i++) cout << answerArray[i][0] << " " << answerArray[i][1] << endl; } int main() { Init(); Solve(); return 0; } Edited by author 02.04.2021 07:26 Edited by author 02.04.2021 07:26 Edited by author 02.04.2021 07:37 Edited by author 02.04.2021 07:37 I use some shamanism ang get AC. Lets see to the next test: 6 0 20 10 50 30 100 60 120 70 130 110 140 my AC prog outputs: 2 10 50 110 140 but right answer of course is: 3 0 20 30 100 110 140 Your tests must be stronger Your test is added. Problem will be rejudged soon. test 6 0 -20 -10 -50 -30 -100 -60 -120 -70 -130 -110 -140 my AC solution have answer 2 -140 -110 -50 -10 on this test, so you've fucked up twice You have fucked up three times with wrong test my answer is : 10 50 60 120 70 130 this problem is quite easy but output is difficult to suitable to right answer !!!!! perhaps i get WA because of it Edited by author 15.03.2009 12:34 Thanks For the test~ I wa#12 and the test helped me. Edited by author 26.11.2009 08:19 6 1 5 2 6 3 7 4 8 5 9 6 10 WHY answer is: 2 1 5 5 9 I think [2;6] and [3;7] have common interior point such as 3, 4, 5, 6. Does anyone know the 8th test? The test is such an input data That if the program behaves as burunduk1 described in his habrahabr.ru post from 2015 It passes the test (And all others tests too) So, sort intervals according to RIGHT endpoints in non-decreasing order. Consider intervals in the sorted order. Let M=max of all right ends added so far. Then if current left end is not less than M then add current interval to answer and update M if current right end is greater than M. Solved both tasks with the same algorithm. Think this task is over-valued. Edited by author 26.10.2016 20:59 If you're doing a greedy solution and you're sorting by the rightmost endpoints (B_i), you need to sort with the leftmost endpoints as second key. That is, if B_i == B_j, the shortest segment of i and j goes first in the list. This basically means that longer segments are kept, so for inputs: 3 3 5 1 5 5 6 You would get result 2 1 5 5 6 instead of 2 3 5 5 6 which means you get a bigger covering of the set but the problem statement didn't mention this requirement. Edited by author 24.12.2014 21:07 there is no such information in statement Change "left" to "remaining" since it would otherwise indicate "the opposite of right" which is confusing Is there somebody who can give me input data for test #2? What's Test 9? My algo is: Search the segment with more intersections and delete it (repeat while the segment got 0 intersections) Is it wrong? yes it is wrong 7 1 3 2 5 2 5 4 7 6 9 6 9 8 10 If you have a problem - WA4 - consider sorting input, not output for example: 5 1 5 3 6 1 3 9 6 4 2 answer 3 1 3 3 6 6 9 I pass the test,But I still got WA#4 thanks for helping me solve WA 1 Edited by author 19.11.2013 20:56 Edited by author 03.11.2013 17:06 This problem is quite easy.You can sort the "end node",and then use the greedy algo to solve the program. Please tell me the reason or give me the t4,thank you! This is my program: #include <cstdio> #include <iostream> #include <cstring> using namespace std; int n,result=0,xia=0,rxia; int line[110][2],era[110][2],fera[110][2]; void init() { int i,j; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d %d",&line[i][0],&line[i][1]); if(line[i][0]>line[i][1]) swap(line[i][0],line[i][1]); } for(i=1;i<n;i++) for(j=i+1;j<=n;j++) { if(line[j][0]<line[i][0]) { swap(line[i][0],line[j][0]); swap(line[i][1],line[j][1]); } if(line[j][0]==line[i][0]) if(line[j][1]<line[i][1]) { swap(line[i][0],line[j][0]); swap(line[i][1],line[j][1]); } } } void jilu(int i) { xia++; era[xia][0]=line[i][0]; era[xia][1]=line[i][1]; } void copyera() { int i; for(i=1;i<=xia;i++) { fera[i][0]=era[i][0]; fera[i][1]=era[i][1]; } } void solve() { int i,x,temp=1,now; for(x=1;x<=n;x++) { xia=0; temp=1; memset(era,0,sizeof(era)); xia++; era[xia][0]=line[x][0]; era[xia][1]=line[x][1]; now=line[x][1]; for(i=x+1;i<=n;i++) if(line[i][0]>=now) { temp++; now=line[i][1]; jilu(i); } if(temp>result) { result=temp; copyera(); rxia=xia; } } printf("%d\n",result); for(i=1;i<=rxia;i++) printf("%d %d\n",fera[i][0],fera[i][1]); } int main() { init(); solve(); return(0); } Thank you very much!!! Maybe you forget sort first just like me. I got AC, but on test: 6 0 30 10 70 20 80 40 110 90 130 120 140 my AC program output: 2 0 30 90 130 but answer must be: 3 0 30 40 110 120 140 Any one who can give some hint? Thanks Try this test 2 1 1 2 Edited by author 24.02.2009 18:43 I think this test must be look like: 1 -999 999 or 2 -999 999 1 4 or 2 0 999 1 4 and other with -999 or/ans 999. P.S.: my bug: for( long key = how[1998]; key != -1; key = how[key] ) AC: for( long key = 1998; key != -1; key = how[key] ) maybe you forgot to write how many lines should be saved. sorry for my poor English |
|