ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1196. History Exam

Time limit exceeded
Posted by Alchimik 24 Aug 2011 03:36
Не знаю английского, извините админы :( Помогите пожалуйста, всё время выскакивает эта ошибка на 8 или на 9 тесте. Пишу на C# помогите оптимизировать код.


using System;

namespace EkzamenIstorii
{
    class Program
    {
        static void Main()
        {
            Work work = new Work();
            work.Start();
        }
    }

    class Work
    {
        int[][] TichersDate;
        int[] UchenikDate;
        int Sovpadenia, buf=0;

        public void Start()
        {
            Input();
            Algoritm();
            Output();
        }

        void Input()
        {

            int CountTichersDates = int.Parse(Console.ReadLine());
            buf = CountTichersDates / 1000;
            buf += 1;
            TichersDate = new int[buf][];
            for (int i = 0; i < buf; i++)
            {
                TichersDate[i] = new int[1];
                for (int j = 0; j < CountTichersDates; j++)
                {

                    TichersDate[i][j] = int.Parse(Console.ReadLine());
                    Array.Resize(ref TichersDate[i], TichersDate[i].Length + 1);
                    if (i == 999)
                    {
                        CountTichersDates -= 1000;
                        break;
                    }
                }

                Array.Resize(ref TichersDate[i], TichersDate[i].Length-1);
            }

            int CountUchenikDate = int.Parse(Console.ReadLine());
            UchenikDate = new int[CountUchenikDate];
            for (int i = 0, j=0; i < UchenikDate.Length; i++)
                UchenikDate[i] = int.Parse(Console.ReadLine());

        }

        void Algoritm()
        {
            for (int k = 0; k < UchenikDate.Length; k++)
            {
                bool flag = false;
                for (int i = 0; i < buf; i++)
                {
                    if (UchenikDate[k] >= TichersDate[i][0] && UchenikDate[k] <= TichersDate[i][TichersDate[i].Length-1])
                        for (int j = 0; j < TichersDate[i].Length; j++)
                            if (UchenikDate[k] == TichersDate[i][j])
                            {
                                Sovpadenia++;
                                flag = true;
                                break;
                            }
                    if (flag) break;
                }
            }
        }

        void Output()
        {
            Console.WriteLine(Sovpadenia);
        }
    }
}
Re: Time limit exceeded
Posted by Valdemar 4 Dec 2011 15:29
Я не знаю СИ шарп, но могу подсказать алгоритм.
Я делал так:
Записываем в массив 1 список преподавателя
Удаляем дубликаты
Начинаем считывать элементы студента по одному(никуда их не записываем), когда считываешь сразу проверяешь есть ли такой в списке преподавателя, если есть то счетчик+1.
Потом просто вывести показания счетчика.
Не знаю как на Си шарп, на С++ пользовался STL получилось за 0.4s и 800kb памяти.
Удачи!
Re: Time limit exceeded
Posted by baku 4 May 2014 11:34
Куда там! Я на Паскале сразу формировала при вводе массив неповторяющихся дат преподавателя, потом так же считывала и сразу искала совпадения студента по преподу и вылетала из цикла поиска. Но!!! 8 тест - тайм лимитед. Может, Паскаль виноват? Потому что на всех моих тестах идет все четко.
Re: Time limit exceeded
Posted by baku 4 May 2014 16:09
var   a:array[1..15000] of longint;
i,n,j,k,flag,b,m:longint;
 k1 :longint;
begin
  k:=0;
  read(n);
read(a[1]);k:=1;
if n>1 then begin
for i:=2 to n do begin
read(b);
flag:=0;
j:=1;
repeat
if a[j]=b then begin flag:=1; end;
j:=j+1;
until (flag=1) or (j>k);
if flag=0 then begin k:=k+1; a[k]:=b;end;
end; end;
read(m);
for i:=1 to m do begin
read(b);
j:=1;    flag:=0;
repeat
if a[j]=b then begin flag:=1; k1:=k1+1;end;
j:=j+1;
until (flag=1) or (j>n);
end;
  writeln(k1);
end.
НО!!! на 8 тесте тайм лимитед. ну, что еще надо??? прохелпите!!! плиз
Re: Time limit exceeded
Posted by kivi* 9 Aug 2014 15:14
Попробуй бинарный поиск
Re: Time limit exceeded
Posted by Sanatbek_Matlatipov 29 Mar 2015 20:09
Thanks Valdemar. This word helped me a lot "Удаляем дубликаты".