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

Обсуждение задачи 1078. Отрезки

Y did I get a WA #2 ? Please help me !
Послано BingoX 20 сен 2010 20:05
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

int a[501][3], f[501], trace[501], n, ans, t;

void sort(int l, int r) {
    int x = a[(l + r) >> 1][0];
    int i, j, t[3];
    i = l;
    j = r;
    do {
        while (a[i][0] < x)
            i++;
        while (a[j][0] > x)
            j--;
        if (i <= j) {
            memcpy(t, a[i], sizeof(t));
            memcpy(a[i], a[j], sizeof(t));
            memcpy(a[j], t, sizeof(t));
        }
        i++;
        j--;
    } while (i <= j);
    if (i < r)
        sort(i, r);
    if (l < j)
        sort(l, j);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &a[i][0], &a[i][1]);
        a[i][2] = i;
    }
    for (int i = 1; i <= n; i++)
        f[i] = 1;
    sort(1, n);
    for (int i = 2; i <= n; i++)
        for (int j = 1; j < i; j++)
            if ((a[j][0] < a[i][0]) && (a[j][1] > a[i][1]) && (f[j] + 1 > f[i])) {
                f[i] = f[j] + 1;
                trace[i] = j;
            }
    ans = 0;
    t = 0;
    for (int i = 1; i <= n; i++)
        if (f[i] > ans) {
            ans = f[i];
            t = i;
        };
    printf("%d\n", ans);
    while (t != 0) {
        printf("%d ", a[t][2]);
        t = trace[t];
    }
    return 0;
}
Re: Y did I get a WA #2 ? Please help me !
Послано SuperLight 20 сен 2010 22:27