I am Getting WA in the Question GCD Condition from Codechef March Long Contest.
Kindly tell me what I've done wrong or some test case where the code produces Wrong answer.

Link for the Question

I Have used RMQ(Range maximum Query) for every prime number

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);
        }
    }
}

firstly i have converted to a structure like the following:-

Example input:- 10 6 20 15 8

(b[i]-->stores the indices of factors of i)

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


Now after implementing RMQ, it will be as follow:-



(cc[i][j][k] stores index of the largest element between b[i][j] and b[i][j+(2^k)-1])

cc[2][0]-->1,2,3,5
cc[2][1]-->1,3,3
cc[2][2]-->3

cc[3][0]-->2,4
cc[3][1]-->4

cc[5][0]-->1,3,4
cc[5][1]-->3


My Code

有帮助吗?

解决方案

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

The output is -1 -1, but gcd(38, 95) = 19, so ans should be 38 1.

Replacing 'break' by 'continue' on line 75 gave AC :)

许可以下: CC-BY-SA归因
不隶属于 StackOverflow
scroll top