1

Codechef March Long Contestの Question GCD ConditionでWA を取得しています。 私が何を間違えたか、またはコードが間違った答えを生成するテストケースを教えてください。

質問へのリンク

すべての素数に 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] の間の最大要素のインデックスを格納します)

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

マイコード

4

1 に答える 1

2

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 4 3 6 28 6 90 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 70 75 76 3 2 3 8 2 30 93
95 95 97

出力は-1 -1ですが、gcd(38, 95) = 19 なので、 ans は38 1になります。

75 行目の「break」を「continue」に置き換えると、AC が返されました :)

于 2014-03-18T15:34:29.613 に答える