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

Обсуждение задачи 1791. Дядя Стёпа и автобусы

WA17
Послано George Agapov 31 окт 2010 02:19
Any ideas, what's wrong? (I used greedy alogorithm)
Re: WA17
Послано vanla 3 апр 2011 18:22
I've this test wrong too. Here's my code:

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
#include <ctime>
using namespace std;

#define forn(i,n) for (int i = 0; i < (int)n; i++)

struct bus {
    int l, r, type, num;
    friend bool operator<(const bus &bus1, const bus &bus2) {
        if (bus1.type != bus2.type) {
            return bus1.r < bus2.r;
        } else {
            return bus1.num < bus2.num;
        }
    }
};

int n, m;
vector<pair<int, int> > v1, v2;
bus mas[300000];

multiset<bus> s;
multiset<bus>::iterator iter;

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    scanf("%d", &n);
    v1.resize(n);
    forn(i,n) {
        scanf("%d%d", &v1[i].first, &v1[i].second);
        v1[i].second += v1[i].first - 1;
    }
    scanf("%d", &m);
    v2.resize(m);
    forn(i,m) {
        scanf("%d%d", &v2[i].first, &v2[i].second);
        v2[i].second += v2[i].first - 1;
    }
    for (int i = 1; i <= n; i++) {
        mas[i].l = v1[i - 1].first;
        mas[i].r = v1[i - 1].second;
        mas[i].type = 1;
        mas[i].num = i;
    }
    for (int i = 1; i <= m; i++) {
        mas[i + n].l = v2[i - 1].first;
        mas[i + n].r = v2[i - 1].second;
        mas[i + n].type = 2;
        mas[i + n].num = i;
    }
    int p1 = 1, p2 = n + 1;
    int t = min(mas[p1].l, mas[p2].l);
    while ((p1 <= n && p2 <= m + n) || t <= 230000000) {
        while (p1 <= n && mas[p1].l <= t) {
            if (mas[p1].r < t) {
                printf("NO");
                return 0;
            } else {
                s.insert(mas[p1++]);
            }
        }
        while (p2 <= m + n && mas[p2].l <= t) {
            if (mas[p2].r < t) {
                printf("NO");
                return 0;
            } else {
                s.insert(mas[p2++]);
            }
        }
        iter = s.begin();
        if (iter != s.end()) {
            if ((*iter).r < t) {
                printf("NO");
                return 0;
            } else {
                s.erase(iter);
            }
            t++;
        } else {
            t = 230000000;
            if (p1 <= n) {
                t = min(t, mas[p1].l);
            }
            if (p2 <= n + m) {
                t = min(t, mas[p2].l);
            }
            if (t == 230000000) {
                printf("YES");
                return 0;
            }
        }
    }
    printf("YES");
    //printf("%.5lf", 1.0 * clock() / (1.0 * CLOCKS_PER_SEC));
}

Where's bug?
Re: WA17
Послано Vit Demidenko 11 май 2014 14:17
1
1 3
2
1 4
1 2

answer is "YES"