Получение WA в ANUGCD от Codechef March Long Contest

Я получаю WA в вопросе GCD Условие от Конкурс Codechef March Long.
Пожалуйста, скажите мне, что я сделал неправильно, или какой-нибудь тестовый случай, когда код дает неправильный ответ.

Ссылка на вопрос

Я использовал RMQ (Range Maximum Query) для каждого простого числа

for(i=0;i<limit;i++)
{
int sz=b[i].size();
if(!sz)continue;
int level=0;
cc[i].resize(sz);
for(j=0;j<sz;j++)cc[i][j].push_back(b[i][j]);//level 0
for(level=1;(1<<level)<=sz;level++)
{
for(j=0;j+(1<<level)<=sz;j++)
{
int c1=cc[i][j][level-1];
int c2=cc[i][j+(1<<(level-1))][level-1];
int mx=(a[c1]<a[c2])?c2:c1;
cc[i][j].push_back(mx);
}
}
}

во-первых, я преобразовал в структуру, как показано ниже:

Пример ввода: — 10 6 20 15 8

(b [i] -> хранит индексы факторов i)

b [2] -> 1,2,3,5
b [3] -> 2,4
b [5] -> 1,3,4

Теперь после внедрения RMQ это будет выглядеть следующим образом:

(cc [i] [j] [k] хранит индекс наибольшего элемента между b [i] [j] и b [i] [j + (2 ^ k) -1])

куб.см [2] [0] -> 1,2,3,5
см [2] [1] -> 1,3,3
см [2] [2] -> 3

куб.см [3] [0] -> 2,4
куб.см [3] [1] -> 4

см [5] [0] -> 1,3,4
см [5] [1] -> 3


Мой код

1

Решение

100 1
88 33 23 56 97 54 8 74 43 95 91 63 38 13 7 7 52 29 6 85 70 15 52 18 78 9 85 51 28 43 4 68 75 78 75 23 32 34 48 74 28 90 36 66 2 95 24 54 23 29 90 45 96 93 14 73 2 99 75 81 93 31 100 19 8 75 93 39 60 41 64 88 30 100 5 84 46 28 89 20 56 30 64 3 22 78 75 75 76 2 8 20 32 7 38 39 33 82 30 93
95 95 97

Выход -1 -1, но gcd (38, 95) = 19, поэтому ответ должен быть 38 1.

Замена ‘break’ на ‘continue’ в строке 75 дала AC 🙂

2

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]