ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 2041. Наноматрёшки

WA 4
Послано Sunnat 15 ноя 2014 15:54
I can't understand my mistake. If you have any test give me please!!!.
Re: WA 4
Послано olpetOdessaONU [1 2/3] 15 ноя 2014 20:04
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
Послано Sunnat 15 ноя 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
Послано olpetOdessaONU [1 2/3] 17 ноя 2014 14:16
Do you use some greedy strategy?
Re: WA 4
Послано Sunnat 25 ноя 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
Послано bsu.mmf.team 25 ноя 2014 15:43
5
2 2
2 2
3 3
3 3
1 4

Your answer: No
Correct answer: Yes, 3 1 5 4 2