Вход | Регистрация

  1  2  3   
Информационные технологии ::

Метки: 

Помогите понять задачу

Я
   DES
 
10.08.18 - 06:39
тестовое задание для абитуры

Раскрашивание точек
ТL =1 секунда
МL=16 мегабайт
Лимит по памяти важен. Далеко не все интерпретируемые языки смогут запустить интерпретатор в этих ограничениях. Выбирайте инструмент в соответствии с задачей
Реализуйте структуру данных, которая может выполнять следующие две операции:
PAINT(х, у, со1) -- покрасить точку (х, у) в цвет соl
QUERY(х, у) — определить цвет точки (х, у).
Покрашенные точки могут быть красными или синими.
Изначально все точки плоскости считаются непокрашенными.
*Известно, что размер любого множества точек, в котором совпадают остатки от деления координат х на 100019, не превосходит 100.

Поясните что им *ИЗВЕСТНО ?
последнее предложение вызывает затруднение понимания.
 
 
   NSSerg
 
101 - 10.08.18 - 14:08
(100) Это обычная фраза задач спортивного программирования.
Когда ты отсылаешь решения, сервер контролирует сколько памяти ты используешь.
https://codeforces.com/problemset
Не поленись, открой любую задачу.
Обязательные атрибуты задачи
//
ограничение по времени на тест:
ограничение по памяти на тест:
   Garykom
 
102 - 10.08.18 - 14:10
Это не ответ - это посылание на некий сайт не имеющий никакого прямого отношения к задаче из (0)
   Garykom
 
103 - 10.08.18 - 14:13
>Ты изобретаешь велосипед. HashMap, Map - Это готовые структуры, которые нужно уметь использовать в спортивном программировании.

Твоя позиция очень похожа на:

Нет готового "HashMap"?
Это не моя проблема я участвую только в "спортивном программировании"
   NSSerg
 
104 - 10.08.18 - 14:15
(103) Я умею реализовать и HashMap и Map.
   Garykom
 
105 - 10.08.18 - 14:17
(104) Так блин дана готовая хеш-функция

"Известно, что размер любого множества точек, в котором совпадают остатки от деления координат х на 100019, не превосходит 100"
   NSSerg
 
106 - 10.08.18 - 14:18
(102) Еще раз - это задача спортивного программирования, поэтому там указан лимит по памяти и по времени. Не более того.
Я тебя отсылаю на сайт, потому что походу ты из лимита по памяти построил странную теорию, из которой следует что нельзя использовать HashMap. А я тебе говорю что это обычное условие задач спортивного программирования. И никакого отношения к запрету HashMap или использованию неких слабых и старых интерпретаторов или компиляторов оно не имеет.
   Garykom
 
107 - 10.08.18 - 14:21
(105)+ Эээ гм не 100 массивов а хз скоко массивов из максимум 100 элементов
   NSSerg
 
108 - 10.08.18 - 14:26
В принципе не принято в спортивном (и не только) программировании решать за О(N^2) задачи которые решаются за О(NlnN). Если это задача на собеседовании - то тебя просто не возьмут на работу.
   Garykom
 
109 - 10.08.18 - 14:28
(108) 10^5 * 100 = ?
укладываемся же!
   NSSerg
 
110 - 10.08.18 - 14:35
(107) Задача в (0) появилась ведь не просто так? А служит для проверки понимания что такое сложность алгоритма. В принципе все задачи спортивного программирования именно это в том числе и проверяют. Ты своим решением хочешь показать что? Что ты не знаешь как эту задачу можно решить за NlnN, а умеешь только за N^2?
Когда будет 10^7 запросов, ты полностью перепишешь решение, чтоб уложиться в 50 секунд?
 
  Рекламное место пустует
   Garykom
 
111 - 10.08.18 - 14:36
(110) Хочешь сказать что это строчка про "...не превосходит 100" в задаче лишняя?
И не подразумевает использование этих знаний например для ручного хеширования?
   NSSerg
 
112 - 10.08.18 - 14:40
(111) Лишняя. Считай что она нужна только для того чтоб запутать.
Кстати, то что ты предлагаешь, разделение массива на множество поменьше - это ну никак не Hash таблица, а больше похоже на  sqrt-декомпозицию.
   Garykom
 
113 - 10.08.18 - 14:42
(112) "sqrt-декомпозиция" - тут и близко не стояла это из какой то совсем другой оперы
   NSSerg
 
114 - 10.08.18 - 14:43
Это условие добавляет  возможность сделать более простое но и более плохое решение. Бывает такое что задача имеет несколько решений, и в зависимости от качества (память, сложность, скорость) решения дается разное количество баллов.
   Garykom
 
115 - 10.08.18 - 14:43
(113)+ Точнее общее только разбиение (но при хеш-функциях это же и происходит) на примерно равные множества, но никаких сумм не надо считать
   NSSerg
 
116 - 10.08.18 - 14:44
(113) sqrt-декомпозиция, это когда для того чтоб быстрее искать, мы по некоторому признаку массив из N элементов делим на много массивов. Примерно Корень из N массивов по корень из N элементов.
А Хеш таблица классическая работает на списках, а не как массив массивов.
   NSSerg
 
117 - 10.08.18 - 14:47
(115) Только что, в (87), ты говорил что не существует структуры с поиском за константное время, а теперь уже стал знатоком хеш-таблиц? :)
   Garykom
 
118 - 10.08.18 - 14:50
(117) любая хеш таблица реализована или на массивах или на списках
Список это частный случай массива когда колво элементов заранее неизвестно

В данной задаче макс колво известно отсюда какой вывод?
   Garykom
 
119 - 10.08.18 - 14:51
(118)+ решать задачу через массивы возможно оптимальнее пусть и сложнее но работать будет быстрее и точнее лимиты на память
   Garykom
 
120 - 10.08.18 - 14:53
(117) обход списка затратнее чем обход массива
   NSSerg
 
121 - 10.08.18 - 14:56
(120) Хеш таблицы не делаются на массивах (точнее делаются, но только когда нам не обязательно избегать коллизий), потому что тогда по каждому адресу тебе нужно держать массив размером на максимальную длину цепочки, на это никакой памяти не хватит.
   Garykom
 
122 - 10.08.18 - 14:58
(121) Если известна максимальная длина цепочки как в данной задаче то?
   NSSerg
 
123 - 10.08.18 - 14:59
(119) Очередная жесть. Решение за (О(N^2)) оптимальнее чем  О(nLnN)? Потому что всегда будет медленней?
Ты разберись со сложностью алгоритма. Что это такое. Решение на HashMap - это решение за О(N). 10^5 операций.
Решение на Map - это решение за 2*10^6 операций.
А твое решение мало того что  медленнее, еще и не рабочее.
   Garykom
 
124 - 10.08.18 - 15:01
(123) Зачем перебирать каждый массив до конца?
Когда можно хранить кол-во заполненных элементов в каждом и цикл только до него.
   Garykom
 
125 - 10.08.18 - 15:04
Судя по чисто нашему диалогу (без участия других) остальные или уже нифига не понимают или им неинтересно ))
   NSSerg
 
126 - 10.08.18 - 15:05
(122) Сколько ты собираешься завести массивов из 100 элементов? 10^5? Опиши еще раз структуру (массивы) которая будет работать не за 10^10 операций, и влезет в память по условию.
(124) Ты точно знаешь что такое сложность алгоритма?
   NSSerg
 
127 - 10.08.18 - 15:05
(125) Судя по нашему диалогу - ты ничего не понимаешь. :)
   Garykom
 
128 - 10.08.18 - 15:06
(126) Завести собираюсь ровно 1000 массивов по 100 элементов
   Garykom
 
129 - 10.08.18 - 15:07
(127) Блин я прекрасно понимаю твое решение и свое решение. Ты понимаешь только свое. И?
   Garykom
 
130 - 10.08.18 - 15:07
(128)+ Еще 1000 целых чисел - кол-во заполненных элементов в каждом из 1000 массивов
   Garykom
 
131 - 10.08.18 - 15:08
(130)+ Естественно в отдельном массиве из 1000 элементов а не 1000 переменных ))
   NSSerg
 
132 - 10.08.18 - 15:08
(128) И по какому признаку ты будешь решать в какой из 100 массивов писать свою пару координат?
   Garykom
 
133 - 10.08.18 - 15:09
(132) "совпадают остатки от деления координат х на 100019"
 
  Рекламное место пустует
   Garykom
 
134 - 10.08.18 - 15:10
(132) Из 1000 массивов
   NSSerg
 
135 - 10.08.18 - 15:15
(133) (134)
Еще раз.
Вот у тебя x и y
Напиши функцию от x и y - которая возвращает число в интервале от 1 до 1000, массив в который ты будешь писать значение цвета по этой координате.
В (133) Ты написал строчку из условия, а не описал свой алгоритм.
   NSSerg
 
136 - 10.08.18 - 15:17
(133) У всех 10^5 пар допустим разные остатки от деления. От 1 до 100000.
   NSSerg
 
137 - 10.08.18 - 15:21
Пары точек x,y
1,1
2,2
и т.д. до
10^5, 10^5
В какой массив попадет каждая из точек?

Ты наверно хочешь сказать что ты сделаешь 100019 массивов по 100 значений. Но тогда ты не влезаешь по памяти.
   Garykom
 
138 - 10.08.18 - 15:29
(137) Об этом я еще не подумал, хз как доказать что будет всего 1000 массивов и/или какую еще хеш-функцию придумать чтоб объединить массивы <100 элементов

когда x от 1 до 1000000000
   Garykom
 
139 - 10.08.18 - 15:31
(137) точек всего 10^5 так что 19 массивов точно лишние
   NSSerg
 
140 - 10.08.18 - 15:38
(139) И как ты до того как получил значение этих 10^5 точек узнаешь какие из массивов лишние? Ты же вроде хочешь сразу объявить двумерный массив. Или это какие-то хитрые массивы, которым можно присваивать индекс в потоке?
   NSSerg
 
141 - 10.08.18 - 15:39
Я так понял, что ты теперь понимаешь что твое решение не укладывается по памяти?
   Garykom
 
142 - 10.08.18 - 15:40
(140) Одного массива 10^5*100 разве не хватит?
   Garykom
 
143 - 10.08.18 - 15:41
(142)+ Двумерный массив 100000 на 100
   NSSerg
 
144 - 10.08.18 - 15:44
(143) И какие у тебя будут исключены остатки по модулю 100019 при заведении массива?

Вот у тебя в потоке первая точка
1,100
Вторая 100019,100
//
В какой элемент массива ты запишешь первую, в какой вторую?
//
10^5*100*8 байт (две координаты, х и y, каждая по 4 байта) это 80 мегабайт.
   Garykom
 
145 - 10.08.18 - 15:46
(144) Входной поток он линейный с последовательным чтением или можно возвращаться к старым элементам но номеру?
   NSSerg
 
146 - 10.08.18 - 15:48
(145) Допустим можно возвращаться.
   Lama12
 
147 - 10.08.18 - 15:48
(23) Спасибо за поправку. Век живи, век учись.

Ну вы монстры... Дочитал до сюда. Вроде понимаю о чем говорите, но блин так это далеко и давно было. И "по кусочкам"...
Вот ТС куда-то слился.
   Garykom
 
148 - 10.08.18 - 15:48
(144) Хм делаем массив 100019 х 100 и x координата задается остатком от деления, внутри храним в 100 элементах только y координату
   Garykom
 
149 - 10.08.18 - 15:51
(148)+ не влазит 40 мегабайт будет ((
 
  Рекламное место пустует
   NSSerg
 
150 - 10.08.18 - 15:52
(148) И как ты отличишь две разные точки, с разным x, но с одинаковым остатком от деления на 100019?
   Garykom
 
151 - 10.08.18 - 15:52
(149)+ Но если можно возвращаться (146) то хранить можно не значение y координаты а номер точки из входных данных
   Garykom
 
152 - 10.08.18 - 15:53
(150) Они рядом будут записаны в 100, их порядковым номером (151)
   NSSerg
 
153 - 10.08.18 - 15:54
(151) Как, ииз какой структуры ты будешь получать номер точки?
Вот у тебя пара запросов на изменение цвкта точки, и один чтение. Тебе каждый раз после первой записи нужно точно определить "порядковый номер точки". Как ты это сделаешь? Хеш-таблицей? Map? :)
   NSSerg
 
154 - 10.08.18 - 15:57
+ (153) Три раза встретилась одна и та-же точка, как ты узнаешь что это одна и та-же точка, если ты не хранишь её координату?
   Garykom
 
155 - 10.08.18 - 16:03
(154) Чем то напоминает задачку на сжатие данных, координаты у нас до 10^9 но точек всего 10^5 можно составить "словарик допустимых координат"

Ответ же нам нужен только цвет R, B или N координату не надо возвращать - их можно не хранить.

Провести при чтении некую замену координат где будет подмена порядкового номера точки встретившегося позднее на самый первый номер этой же точки (с этими же координатами).
   Cyberhawk
 
156 - 10.08.18 - 16:08
"координаты у нас до 10^9" // Орицательные тоже могут быть. Т.е. координата по У ограничена только сверху, а по Х - только слева (больше нуля, типа). Плюс есть ограничение на размер области по высоте и ширине, описанные мною ранее
   Garykom
 
157 - 10.08.18 - 16:09
(156) 0 <= x,y <= 10^9
https://prnt.sc/kgyyos
   Cyberhawk
 
158 - 10.08.18 - 16:11
И Я про то же. Не ясно, зачем ты это написал.
   Garykom
 
159 - 10.08.18 - 16:11
(158) Не может быть отрицательных координат x или y
   NSSerg
 
160 - 10.08.18 - 16:12
(155) Ты понимаешь что элементарную задачу, которая решается начинающим программистом, джуниором - минут за 5 - ты превратил невесть в что, и до сих пор не выдал рабочего решения укладывающегося в лимиты?
Когда есть решение в ветке за О(N), на hashMap, и понятно что при N элементах в потоке - решения с лучшей асимптотикой быть не может. Так как на чтение из потока нужно О(N) операций.
(156) В условии написано: 0<=x,y<=10^9
Эта запись означает что обе координаты меньше либо равны 10^9, и обе больше либо равны нулю.
   Cyberhawk
 
161 - 10.08.18 - 16:13
(159) (160) Это одна из двух возможных трактовок
   Garykom
 
162 - 10.08.18 - 16:16
(160) Для решения на hashMap, ты ключом что будешь делать?

Сколько будет операций при добавлении новых значений в 10^5 HashMap или получении значения оттуда?
Число 10 операций откуда взялось?
   NSSerg
 
163 - 10.08.18 - 16:25
(162) 10 это двоичный логарифм от 1000. К hashmap это не имеет никакого значения. Это количество операций для поиска и добавления значения в "map" (бинарное дерево) с 1000 элементами.
//
В HashMap добавление и чтение это О(1) - константа. Одна операция.
Для добавления 10^5 значений в HashMap потребуется 10^5 (О(10^5)) операций.
   Garykom
 
164 - 10.08.18 - 16:25
(162)+ Ключ (x+y) записываем в 8 байт, еще 1 байт для цвета.
Макс элементов 10^5 итого 10^5 * 9 = 900 килобайт.

Но не учитываются накладные расходы на хранение списка ключей и списка значений, а они для 10^5 элементов будут немаленькие.
https://habr.com/post/159557/
   Garykom
 
165 - 10.08.18 - 16:26
(163) >В HashMap добавление и чтение это О(1) - константа. Одна операция.

Офигеть а за сколько времени выполняется эта одна операция в мс?
   Garykom
 
166 - 10.08.18 - 16:29
(165) Я выше приводил картинку где есть размеры коллекций и быстродействие
   Garykom
 
167 - 10.08.18 - 16:29
   NSSerg
 
168 - 10.08.18 - 16:33
(165) Неважно. Там константа конечно больше чем в map, но не на много.
Около 10^-6 сек.
(166) И что ты понял из этой картинки? Что реализация HashMap не очень хорошая, и сложность конечно заметно меньше логарифма, но чуть хуже чем О(1)?
А хорошая реализация в LinkedHash?
Ну и что?
   NSSerg
 
169 - 10.08.18 - 16:35
До 50000 элементов , а это и есть почти 10^5, как и есть в условии - скорость доступа 1микросекунда, 10^-6. Зависимость становится чуть хуже чем константа на намного больших размерах.
   NSSerg
 
170 - 10.08.18 - 16:39
(164) Немаленькие это в 20 раз больше, или максимум в два раза больше? По условию у нас лимит до 15 мегабайт.
(162) Это очень странный вопрос. Конечно
typedef pair<uint, uint> Key;
   NSSerg
 
171 - 10.08.18 - 16:46
Всё было описано выше. На хранение каждой точки нужно 9 байт. Итого потребуется 900 килобайт, ну и естественно плюс накладные расходы. Допустим даже в 10 раз больше. Все-равно укладываемся.
Не укладываешься - так поменяй в коде hashmap на map, делов то. Будет чуть медленней, на логарифм, но места будет занимать меньше.
   Garykom
 
172 - 10.08.18 - 16:52
(171) Угу 3 мегабайта накладных расходов примерно
   Digger
 
173 - 10.08.18 - 17:25
(147)  +1
Почитал, как будто снова окунулся в детство.  Все это было, но блин так давно. Чувствую уже давно стал "не программистом",  совсем мозг заплыл адинэсом. )
   NSSerg
 
174 - 10.08.18 - 17:36
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef pair<unsigned int, unsigned int> Key;
struct pair_hash {
    template <class T1, class T2>
    std::size_t operator () (const pair<T1,T2> &p) const {
        auto h1 = hash<T1>{}(p.first);
        auto h2 = hash<T2>{}(p.second);
        return h1 ^ h2;  
    }
};
int main()
{
    std::ios::sync_with_stdio(false);
    unordered_map <Key,char,pair_hash> a;
    int n;
    int op;
    unsigned int x,y;
    char c;
    cin >> n;
    for(int i=0;i<n;i++) {
      cin >> op >> x >> y;
      if (op==1) { cin >> c; a[make_pair(x,y)]=c;} else
      {
      auto f=a.find(make_pair(x,y));      
      if (f==a.end()) cout << 'N'; else
        cout << f->second << "\n";
      }
    }
    cout.flush();
    return 0;
}
Вот код,
если не нравятся Хеш-таблицы, достаточно unordered_map поменять на map
   NSSerg
 
175 - 10.08.18 - 21:39
виноват, косяк, забыл перевод строки, в тестовом примере ‘N’ в последней строке, поэтому глюк не заметил
auto f=a.find(make_pair(x,y));      
      if (f==a.end()) cout << 'N' << "\n"; else
        cout << f->second << "\n";
   DES
 
176 - 10.08.18 - 22:16
это на каком ЯП??
   NSSerg
 
177 - 10.08.18 - 22:18
(176) C++
можешь проверить на любом онлайн компиляторе. Я так и проверял на тех входных данных которые на твоем скриншоте задания.
могу написать на другом ЯП. На каком надо?
   Cyberhawk
 
178 - 10.08.18 - 22:20
(177) На 1С давай, чтоб всем понятно было )
   NSSerg
 
179 - 10.08.18 - 22:25
(178) на 1с слишком просто.
только условие не выполнить, 1с не умеет читать из консольного ввода.
   Lama12
 
180 - 10.08.18 - 22:41
(176) Извиняюсь, а точно имеет смысл абитура?
Конечно ИМХО, но С++ хорошо бы знать в лицо.
Очень рекомендую.
   DES
 
181 - 11.08.18 - 08:44
(177) на с
   DES
 
182 - 11.08.18 - 08:46
(177) и еще …
в задании указаны условия, нужно ли в решения делать проверку условий или условия указаны для понимания объема данных и ресурсов
   NSSerg
 
183 - 11.08.18 - 08:52
(182) нет, проверку делать не надо. все условия написаны для того чтоб понимать что может быть во входном потоке.

код на C++11, он немного ускоряет написание по сравнению с чистым C++
   DES
 
184 - 11.08.18 - 09:05
нужен чистый классический С
   DES
 
185 - 11.08.18 - 09:07
(179) 1с умеет же читать с консоли
ВвестиЧисло
   NSSerg
 
186 - 11.08.18 - 09:21
(185) это не то :)
вечером, освобожусь, напишу на си
задачу можно решить без использования индексов, бинарных деревьев и хеша, на списках.
заводим массив на 100019 элементов, в который пишем ссылку  в списке на первую точку с заданным остатком от деления x на 100019.
а в списке (общем для всех точек) с каждой точкой хранится ссылка на следующую точку с таким же остатком от деления.
итого у нас на поиск каждой точки уйдет не больше 100 операций.
И в лимит по памяти легко уложились.
   DES
 
187 - 11.08.18 - 09:43
т.е. мы вычислили что объем массива не более 100019 ?
   DES
 
188 - 11.08.18 - 09:44
я не понял в чем фишка остатка от деления. что это определяет?
   NSSerg
 
189 - 11.08.18 - 10:17
(187) В условии написано что таких чисел не больше ста.
У нас есть точка с координатой x,y
Если мы будем искать её в нашей структуре только среди точке с остатком отделения x на 100019 таким-же как и у текущей точки, то потратим на это не более 100 операций, потребуется перебрать не больше 100 точке.

Структуры для хранения две.
Первая - массив на 100019 элементов, по два байта на значение - ссылка на первый элемент с заданным остаток от деления в списке.
Вторая - связный список, на N+1 элементов
(максимум на 100001). Для удобства нулевой элемент использовать не будем, 0 - это будет пустая ссылка.
В котором хранятся координаты x и y (8 байт), цвет (1 байт), и ссылка на следующий номер элемента в этом массиве с таким-же остатком от деления x на 1000019 (2 байта)
Итого 100001*11+100019*2 байт, чуть больше мегабайта.
Связный список сделаем на массиве - для скорости. Чтоб не выделять память по одному элементу.
   NSSerg
 
190 - 11.08.18 - 10:23
+(189) То есть мы по сути реализуем хеш-таблицу, где в качестве хеша используется остаток от деления координаты x на 100019. Как и хотел Garykom, но у него что-то не получилось :)
   NSSerg
 
191 - 11.08.18 - 10:46
Виноват, все ссылки по 4 байта.
   NSSerg
 
192 - 11.08.18 - 12:39
#define size 100019
#define maxN 100001
#include <stdio.h>
#include <stdlib.h>
typedef unsigned long int UINT;
typedef struct node
{
    UINT x,y,next;
    char c;
};
struct node List[maxN];
UINT Hash[size];
UINT ListN=0;
char QUERY(UINT x, UINT y)
{
    UINT p=Hash[x%size];
    while (p!=0)
    {
        struct node Node=List[p];
        if ((Node.x==x)&&(Node.y==y)) return Node.c;
        p=Node.next;
    }
    return 'N';
}

void PAINT(UINT x, UINT y, char col)
{
    UINT p=Hash[x%size];
    while (p!=0)
    {
        if ((List[p].x==x)&&(List[p].y==y))
        {
            List[p].c=col;
            return;
        }
        p=List[p].next;
    }
    List[++ListN].x=x;
    List[ListN].y=y;
    List[ListN].c=col;
    List[ListN].next=Hash[x%size];
    Hash[x%size]=ListN;
}
int main()
{
    int i;
    for (i=0; i<size; i++) Hash[i]=0;
    int n;
    scanf("%d",&n);
    UINT op,x,y;
    char c;
    for (i=0; i<n; i++)
    {
        scanf("%lu%lu%lu",&op,&x,&y);
        if (op==1)
        {
            do
            {
                scanf("%c",&c);
            }
            while ((c!='R')&&(c!='B'));
            PAINT(x,y,c);
        }
        else
            printf("%c\n",QUERY(x,y));
    }
    return 0;
}
   NSSerg
 
193 - 11.08.18 - 12:42
#define size 100019
#define maxN 100001
#include <stdio.h>
#include <stdlib.h>
typedef unsigned long int UINT;
typedef struct node
{
    UINT x,y,next;
    char c;
};
struct node List[maxN];
UINT Hash[size];
UINT ListN=0;
char QUERY(UINT x, UINT y)
{
    UINT p=Hash[x%size];
    while (p!=0)
    {
        if ((List[p].x==x)&&(List[p].y==y)) return List[p].c;
        p=List[p].next;
    }
    return 'N';
}

void PAINT(UINT x, UINT y, char col)
{
    UINT p=Hash[x%size];
    while (p!=0)
    {
        if ((List[p].x==x)&&(List[p].y==y))
        {
            List[p].c=col;
            return;
        }
        p=List[p].next;
    }
    List[++ListN].x=x;
    List[ListN].y=y;
    List[ListN].c=col;
    List[ListN].next=Hash[x%size];
    Hash[x%size]=ListN;
}
int main()
{
    int i;
    for (i=0; i<size; i++) Hash[i]=0;
    int n;
    scanf("%d",&n);
    UINT op,x,y;
    char c;
    for (i=0; i<n; i++)
    {
        scanf("%lu%lu%lu",&op,&x,&y);
        if (op==1)
        {
            do
            {
                scanf("%c",&c);
            }
            while ((c!='R')&&(c!='B'));
            PAINT(x,y,c);
        }
        else
            printf("%c\n",QUERY(x,y));
    }
    return 0;
}

Так единообразней. По сути это реализация простейшей Хеш-таблицы.
   NSSerg
 
194 - 11.08.18 - 14:07
В typedef struct node - typedef лишнее. Нужно писать
typedef unsigned long int UINT;
struct node
{
    UINT x,y,next;
    char c;
};
struct node List[maxN];
   kyvv
 
195 - 11.08.18 - 17:03
ТС ты не одинок, но я не поступаю :)
"Известно, что размер любого множества точек, в котором совпадают остатки от деления координат х на 100019, не превосходит 100"

...множество(из пар х и у), в котором совпадают остатки от деления координат х на const = 100019 (x1/const=xN/const). Или  хто там должЁн совпасть?
   kyvv
 
196 - 11.08.18 - 17:27
NSSerg слился, ...
   kyvv
 
197 - 11.08.18 - 17:59
Да и фиг с ней.
   NSSerg
 
198 - 11.08.18 - 18:07
(196) в смысле?
   kyvv
 
199 - 11.08.18 - 18:26
(198) из ветки. Понятно, что мастера тупняки достали.
   NSSerg
 
200 - 11.08.18 - 18:29
(177) на вход подаются в том числе запросы на добавление точек, с координатами (x,y)
И разных точек, но при этом с одинаковым x%100019  - не может быть больше ста.

  1  2  3   

Список тем форума
 
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Рекламное место пустует