|
|
back to boardWA 4 Posted by Sunnat 15 Nov 2014 15:54 I can't understand my mistake. If you have any test give me please!!!. Re: WA 4 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 Re: WA 4 Posted by Sunnat 15 Nov 2014 22:51 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 Re: WA 4 Do you use some greedy strategy? Re: WA 4 Posted by Sunnat 25 Nov 2014 12:39 #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 Re: WA 4 5 2 2 2 2 3 3 3 3 1 4 Your answer: No Correct answer: Yes, 3 1 5 4 2 |
|
|