|
|
back to boardI can't understand my mistake. If you have any test give me please!!!. Try one of these tests. I'm sure, your program gets 'No' on exactly one of them: 6 4 4 4 4 2 4 1 5 3 3 3 3 6 2 4 2 2 2 2 3 3 3 3 1 5 answer: 6 4 4 4 4 2 4 1 5 3 3 3 3 Yes 1 4 2 5 3 6 6 2 4 2 2 2 2 3 3 3 3 1 5 Yes 4 1 5 2 6 3 Do you use some greedy strategy? #include <algorithm> #include <stdio.h> #include <set> using namespace std; #define _1 first #define _2 second #define mk make_pair typedef pair<int, int> PII; typedef pair<int, PII> PIII; bool cmp(PIII a, PIII b){ return a._2._1 != b._2._1 ? a._2._1 > b._2._1 : a._1 > b._1; } const int maxn = 100005; PIII a[maxn]; PII b[maxn]; int res[maxn], endres; int main(){ int n,q; set<PII>myset; scanf("%i",&n); endres = n - 1; for(int i = 0; i < n; i ++){ scanf("%i %i",&a[i]._1, &a[i]._2._1); a[i]._2._2 = i + 1; } sort(a,a + n, cmp); res[endres] = a[n - 1]._2._2; b[endres] = mk(a[n - 1]._1, a[n - 1]._2._1); endres --; for(int i = n - 2; i >= 0; i --){ if(!myset.empty()){ set<PII> :: iterator it; it = myset.lower_bound(mk(a[i]._1, 1000001)); while(it != myset.end() && (*it)._1 == a[i]._1) it --; if(it != myset.end()){ PII pr = *it; //printf("%i\n", (*it1).second) res[pr._2] = a[i].second.second; b[pr._2] = mk(a[i]._1, a[i]._2._1); myset.erase(it); continue; } } if(res[endres + 1] == 0 || b[endres + 1]._1 != a[i]._2._1){ res[endres] = a[i]._2._2; b[endres] = mk(a[i]._1,a[i]._2._1); }else { myset.insert(mk(a[i]._2._1, endres)); endres --; res[endres] = a[i]._2._2; b[endres] = mk(a[i]._1,a[i]._2._1); } endres --; } if(myset.empty()){ puts("Yes"); for(int i = 0; i < n; i ++) printf("%i ",res[i]); } else puts("No"); return 0; } can you give me any test for this code. I have got WA# 4 5 2 2 2 2 3 3 3 3 1 4 Your answer: No Correct answer: Yes, 3 1 5 4 2 |
|
|