На этих выходных состоится второй этап VIII Открытого Кубка по программированию им. Е. В. Панкратьева. Основной день для написания - 19 сентября в 11:00 MSD. Всем удачи
→ Обратите внимание
До соревнования
Refact.ai Match 1 (Codeforces Round 985)
4 дня
Зарегистрироваться »
Refact.ai Match 1 (Codeforces Round 985)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 05.11.2024 06:53:24 (j3).
Десктопная версия, переключиться на мобильную.
При поддержке
Проще всего как-то так: разобьём планеты на максимальные по включению интервалы (т.е. если попали в интервал, то его весь облететь сможем, а всё остальное -- уже нет) и оффлайн обработаем все запросы.
6
+6
+8
-6
-8
+9
+3
6 2 8 1 1 1 или 6 2 8 1 9 3
var n,i,lik,nod,kol,t,op:longint;
a:array of longint;
b:array of longint; sim:char;
function nodob(a,b:longint):longint;
begin
while (a<>0) and (b<>0) do
if a>b then a:=a mod b else b:=b mod a;
nodob:=a+B;
end;
procedure Swap(Var t,y:longint);
var u:longint;
begin u:=t; t:=y; y:=u; end;
procedure Sort(l,r:longint);
var i,j,x:longint;
begin
x:=a[(l+r) div 2]; i:=l; j:=r;
repeat
while a[i]<x do inc(i);
while a[j]>x do dec(j);
if i<=j then begin Swap(a[i],a[j]); Swap(b[i],b[j]); inc(i); dec(j); end;
until i>j;
if l<j then Sort(l,j);
if i<r then Sort(i,r);
end;
function BIN(lik:longint):longint;
var l,r,sredn:longint;
begin
l:=1; r:=kol; sredn:=(l+r) div 2;
while r-l>1 do
begin
if a[sredn]=lik then begin Bin:=sredn; exit; end
else
if lik<a[sredn] then r:=sredn else l:=sredn;
sredn:=(l+r) div 2;
end;
if a[l]=lik then begin BIN:=l; exit; end;
if a[l+1]=lik then begin BIN:=l+1; exit; end;
BIN:=0;
end;
begin
assign(input,'input.txt');
reset(input);
assign(output,'output.txt');
rewrite(output);
readln(n);
SetLength(a,n+2);
SetLength(b,n+2);
kol:=0; NOD:=0;
for op:= 1 to n do
begin
readln(sim,lik);
case sim of
'+':begin
t:=BIN(lik);
if t=0 then begin
inc(kol);
a[kol]:=lik; b[kol]:=1;
Sort(1,kol);
if kol=1 then nod:=lik else
nod:=nodob(nod,lik);
end else
begin
inc(b[kol]);
end;
end;
'-':begin
t:=BIN(lik);
if b[t]>1 then begin
dec(b[t]);
end else
begin
a[t]:=0; b[t]:=0;
for i:= t to kol-1 do
begin
a[i]:=a[i+1];
b[i]:=b[i+1];
end;
dec(kol);
if kol=0 then begin nod:=1;
end else
begin
nod:=a[1];
for i:= 2 to kol do
begin
nod:=nodob(nod,a[i]);
if nod=1 then break;
end;
end;
end;
end;
end;
writeln(nod);
end;
close(inpuT); close(output);
end.
Почему у меня WA на 4 тесте.
1. Запоминал не только какое число добавлял, но и его количество.
2. При считывании входных данных если «+», и элемента ещё не было, искал НОД добавляемого числа и уже имеющийся НОД.
3. При «-», если такое число было в списке, ничего не делал, если удаляемое число являлось последним – пересчитывал НОД начиная с самых маленьких чисел.
4. Все мною созданные тесты программа проходит. Но все равно WA на 4 тесте.
Я нашёл свою ошибку и теперь у меня TLE на 17 тесте. Мне кажется что эту задачу простым массивом не сделаешь, а необходимо строить декартово дерево для ускорения работы по массиву. Или я не прав?
Я даже не знаю как её можно ускорить. Все ресурсы исчерпал.
Теперь напиши всё то же самое, то операцией сделай НОД.
Для каждого такого вектора v, разобьем всех кроликов на классы эквивалентности относительно этого вектора. (отношение эквивалентности: A~B - |A-B| || v.
Отсортируем точки внутри каждого класса эквивалентности по x, потом по y. Теперь мы для запроса мы можем определить: класс эквивалентности в котором лежит точка выстрела за O(1), и сколько точек лежит на этом луче O(log n) - бинарным поиском.
Как по точке (x, y)определить класс эквивалентности относительно вектора (a, b): с = -b * x + a * y;
Для выбранного направления достаточно посортить все точки как если бы это направление было осью абсцисс и дальше бинпоиском найти то, что просят.
Нет, там главное, - понять, что из-за МСТшности степень каждой вершины небольшая. Вооружившись этим фактом, понятно, что можно писать динамику по маскам в каждой вершине, либо даже всякое палево типа random_shuffle :)
Почему степень маленькая? Можно понять, что максимальная она - когда у текущей вершины ровно 6 соседей, расположенных в виде правильного 6-угольника (потому что тогда каждый треугольник, образованный двумя соседями и самой вершиной, является правильным), а если их больше - то уже становится невыгодно соединять соседей именно с текущей вершиной (как-нибудь по неравенству треугольников что ли доказать это можно). На самом деле, в тестах и вовсе все степени не превосходят пяти, поскольку 6-угольник сделать из челочисленных координат, мягко говоря, проблематично :)