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

Обсуждение задачи 1105. Раскраска наблюдателей

wa5. help
Послано Ibragim Atadjanov (Tashkent U of IT) 12 ноя 2010 04:01
I got wa5. I cant find my bug. please help to find my bug or
give me the test my prog fail

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Locale;

public class Timus1105 {

    private static StreamTokenizer st;
    private static double l;
    private static int n;
    private static ArrayList<Interval> list;

    public static void main(String[] args) {
        Locale.setDefault(Locale.US);
        st = new StreamTokenizer(new InputStreamReader(System.in));
        l = - nextDouble() + nextDouble();
        n = nextInt();
        list = new ArrayList<Interval>();

        for (int i = 0; i < n; i++) {
            list.add(new Interval(nextDouble() , nextDouble(), i + 1));

        }
        Collections.sort(list);
        for (int i = 1; i < list.size() ; ) {
            if(list.get(i).r <= list.get(i - 1).r){
                list.remove(i);
            }
            else{
                if(i < list.size() - 1 && list.get(i).r < list.get(i + 1).r && list.get(i + 1).l <= list.get(i - 1).r){
                    list.remove(i);
                }
                else
                    i++;
            }
        }
        double sum1 = 0;
        double sum2 = 0;
        for (int i = 0; i < list.size(); i++) {
            if(i % 2 == 0){
                sum1 += list.get(i).r - list.get(i).l;
            }
            else{
                sum2 += list.get(i).r - list.get(i).l;
            }
        }


        for (int i = 0; i < list.size() - 1; i++) {
            double r = Math.min(list.get(i).r, list.get(i + 1).l);
            double l = Math.max(list.get(i + 1).l, list.get(i).r);
            list.get(i).r = r;
            list.get(i + 1).l = l;
        }

        double sum = 0;
        ArrayList<Integer> ans = new ArrayList<Integer>();
        for (int i = 0; i < list.size(); i++) {
            double x = list.get(i).r - list.get(i).l;
            if(x > 0){
                sum += x;
                ans.add(list.get(i).i);
            }
        }

        if(sum1 > sum ){
            sum = sum1;
            ans.clear();
            for (int i = 0; i < list.size(); i+=2) {
                ans.add(list.get(i).i);
            }
        }
        if(sum1 > sum){
            sum = sum2;
            ans.clear();
            for (int i = 1; i < list.size(); i+=2) {
                ans.add(list.get(i).i);
            }
        }
        if(3 * sum >= 2 * l){
            System.out.println(ans.size());
            for (int i = 0; i < ans.size(); i++) {
                System.out.println(ans.get(i));
            }
        }
        else{
            System.out.println(list.size());
            for (int i = 0; i < list.size(); i++) {
                System.out.println(list.get(i));
            }
        }
    }

    static double nextDouble(){
        try {
            st.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return st.nval;
    }

    static int nextInt(){
        try {
            st.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int) st.nval;
    }

    static class Interval implements Comparable<Interval>{
        double l, r;
        int i;

        Interval(double l1, double r1, int i1){
            l = l1;
            r = r1;
            i = i1;
        }

        @Override
        public int compareTo(Interval o) {
            int ret = (int) (this.l - o.l);
            if(ret == 0){
                ret = (int) (o.r - this.r);
            }
            return ret;
        }


    }
}