Блог пользователя Vlad_Zhukov

Автор Vlad_Zhukov, 12 лет назад, По-русски

Уже несколько месяцев учу Java, но так и не могу научиться понимать какие задачи ей решить нельзя из-за времени работы. Вот условия задачи: http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=1041&chapterid=1338#1 Решил все по разбору(он есть там же по ссылке), с асимптотикой все ок. Сделал вывод, что это из-за времени работы java.

Т_ак можно ли как-то ускорить мое решение, чтобы оно зашло или все-таки писать на другом языке?_

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;



public class NGU_Building {	
	class Event{
		int type, area, z;
		Event(int t, int s, int pos){
			type = t;
		    area = s;
		    z = pos;
		}
	}
	
	class SortByZ implements Comparator<Event>{

		@Override
		public int compare(Event a, Event b) {
			if (a.z > b.z)
				return 1;
			else
				if (a.z < b.z)
					return -1;
				else
					if (a.type < b.type)
						return 1;
					else
						if(a.type > b.type)
							return -1;
						else
							return 0;
		}
		
	}

	BufferedReader in;
	PrintWriter out;
	StringTokenizer st;
	final int MaxN = 200000;
	
	void solve() throws IOException {
		int n = nextInt();
		int w = nextInt();
		int l = nextInt();
		Event[] events = new Event[2 * n];
		Event[] events1 = new Event[2 * n];
		for (int i = 0; i < n; i++){
			int x1 = nextInt();
			int y1 = nextInt();
			int z1 = nextInt();
			int x2 = nextInt();
			int y2 = nextInt();
			int z2 = nextInt();
			int area = (x2 - x1) * (y2 - y1);
			events[2 * i] = new Event(0, area, z1);
			events[2 * i + 1] = new Event(1, area, z2);
			events1[2 * i] = new Event(0, area, z1);
			events1[2 * i + 1] = new Event(1, area, z2);
		}
		Arrays.sort(events, new SortByZ());
		int s = 0;
		int k = 0;
		int mink = MaxN;
		int minz = -1;
		for (Event i: events){
			if (i.type == 0){
				s += i.area;
				k++;
			}
			else{
				s -= i.area;
				k--;
			}
			if (s == w * l){
				if (k < mink){
					mink = k;
					minz = i.z;
				}
			}
		}
		if (minz == -1){
			out.println("NO");
			return;
		}
		out.println("YES");
		out.println(mink);
		
		for (int i = 0; i < n; i++){
			if (events1[2 * i].z <= minz && events1[2 * i + 1].z > minz)
				out.println(i + 1);
		}
	}

	void run() throws IOException {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(new OutputStreamWriter(System.out));

		solve();

		in.close();
		out.close();
	}

	public static void main(String[] args) throws IOException {
		new NGU_Building().run();
	}

	String nextToken() throws IOException {
		while (st == null || !st.hasMoreTokens()) {
			st = new StringTokenizer(in.readLine());
		}
		return st.nextToken();
	}

	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}

}
  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Сделай random_shuffle массива перед тем, как сортить. Java QuickSort в худшем случае работает O(N^2)

»
12 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Самая затратная операция тут — сортировка массива из 200000 event-ов. Видимо, informatics.mccme.ru очень не любит Java и автоматически проставляет всем решениям на Java вердикт TL. Сдавайте задачи на Codeforces, Timus, acm.sgu.ru и будет вам счастье

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    это задача со всероса. Вот получается на всеросе такие же ограничения и там тоже мое решение не пройдет?

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Ну там наверное сервер и тестирующая система нормальные, не?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    нормально делай — нормально будет! сервер на informatics.mccme.ru довольно быстрый (вполне себе быстрый), так что скорее всего автор что-то не так написал

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Надо смотреть что именно тормозит. Неожиданно, да? ;-)

Вроде вон у вас над заданием указано что даже Пытон заходит, а он куда как тормознее. Тут при N=100тыщ три цикла O(N) и одна сортировочка встроенная. Конечно я не знаю что за проверяющий сервер, но вряд ли Pentium-II... ;-)

Может вывод тормозит? Можно начать с

new PrintStream(System.out, false); вместо вашего PrintWriter... Можно и PrintWriter, но автофлаш надо отключить всё равно.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Вот, да, надо посмотреть, что за OutputStreamWriter такой, может в нем правда есть автофлаш? Я всегда создавал new PrintWriter(System.out) — там автофлаш не делается.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Как я понял для питона расширили тайм-лимиты. ср. время 5.402

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    new PrintStream(System.out, false); наоборот замедлил

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Ну ты-таки расставь засечки времени между ответственными кусками метода solve. И расскажи где основное торможение. Что по шагам так и тестить "замени там — заменил, нипамагаит"?

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

По-моему, у вас тормозит создание 400000 объектов, попробуйте обойтись 200000.

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Зашло только с руками написанной сортировкой... Но в вашем коде и без этого можно написать events1[2 * i] = events[2 * i] вместо создания двух одинаковых объектов, а также вместо for'а с итератором написать обычный.

»
12 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

рожу на фото попроще сделай

»
12 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

В данном случае, более профессиональный подход таков:

  1. Скачать тесты с neerc.ifmo

  2. Запустить у себя локально и найти тест, на котором дольше всего работает.

  3. Вставить внутрь кода вывод времени, чтобы понимать, какая часть кода дольше всего работает (ввод, создание событий, сортировка, вывод, еще что-то...)

  4. Оптимизить и спрашивать уже про нужную часть.

Даже если задачка уже зашла, еще не поздно проделать описанное выше и, возможно, удивиться ;-)