結果

問題 No.2102 [Cherry Alpha *] Conditional Reflection
ユーザー sapphire__15sapphire__15
提出日時 2022-08-13 02:55:12
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 567 ms / 3,000 ms
コード長 2,162 bytes
コンパイル時間 2,061 ms
コンパイル使用メモリ 97,268 KB
実行使用メモリ 52,540 KB
最終ジャッジ日時 2023-08-24 16:39:28
合計ジャッジ時間 35,439 ms
ジャッジサーバーID
(参考情報)
judge14 / judge15
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 19 ms
20,220 KB
testcase_01 AC 18 ms
20,228 KB
testcase_02 AC 344 ms
33,728 KB
testcase_03 AC 364 ms
34,784 KB
testcase_04 AC 371 ms
34,108 KB
testcase_05 AC 314 ms
29,464 KB
testcase_06 AC 392 ms
34,456 KB
testcase_07 AC 203 ms
28,224 KB
testcase_08 AC 196 ms
24,088 KB
testcase_09 AC 303 ms
32,756 KB
testcase_10 AC 225 ms
26,604 KB
testcase_11 AC 142 ms
26,284 KB
testcase_12 AC 276 ms
30,316 KB
testcase_13 AC 370 ms
35,408 KB
testcase_14 AC 332 ms
30,736 KB
testcase_15 AC 438 ms
35,344 KB
testcase_16 AC 494 ms
38,520 KB
testcase_17 AC 152 ms
26,460 KB
testcase_18 AC 258 ms
29,768 KB
testcase_19 AC 232 ms
28,100 KB
testcase_20 AC 401 ms
36,276 KB
testcase_21 AC 326 ms
27,052 KB
testcase_22 AC 506 ms
39,780 KB
testcase_23 AC 524 ms
39,884 KB
testcase_24 AC 517 ms
39,664 KB
testcase_25 AC 540 ms
39,796 KB
testcase_26 AC 525 ms
39,692 KB
testcase_27 AC 503 ms
39,656 KB
testcase_28 AC 514 ms
39,712 KB
testcase_29 AC 514 ms
39,712 KB
testcase_30 AC 524 ms
39,680 KB
testcase_31 AC 517 ms
39,796 KB
testcase_32 AC 518 ms
39,832 KB
testcase_33 AC 518 ms
39,712 KB
testcase_34 AC 508 ms
39,720 KB
testcase_35 AC 517 ms
39,664 KB
testcase_36 AC 508 ms
39,808 KB
testcase_37 AC 514 ms
39,736 KB
testcase_38 AC 519 ms
39,692 KB
testcase_39 AC 518 ms
39,688 KB
testcase_40 AC 527 ms
39,640 KB
testcase_41 AC 512 ms
39,684 KB
testcase_42 AC 333 ms
33,376 KB
testcase_43 AC 335 ms
33,356 KB
testcase_44 AC 336 ms
33,376 KB
testcase_45 AC 336 ms
33,484 KB
testcase_46 AC 334 ms
33,452 KB
testcase_47 AC 234 ms
27,624 KB
testcase_48 AC 238 ms
27,664 KB
testcase_49 AC 235 ms
27,724 KB
testcase_50 AC 237 ms
27,848 KB
testcase_51 AC 237 ms
27,812 KB
testcase_52 AC 82 ms
52,540 KB
testcase_53 AC 79 ms
52,504 KB
testcase_54 AC 79 ms
52,420 KB
testcase_55 AC 95 ms
22,612 KB
testcase_56 AC 96 ms
22,456 KB
testcase_57 AC 95 ms
22,604 KB
testcase_58 AC 83 ms
36,836 KB
testcase_59 AC 567 ms
44,496 KB
testcase_60 AC 195 ms
23,632 KB
testcase_61 AC 94 ms
22,456 KB
testcase_62 AC 29 ms
20,752 KB
testcase_63 AC 143 ms
24,200 KB
testcase_64 AC 143 ms
24,260 KB
testcase_65 AC 143 ms
24,204 KB
testcase_66 AC 93 ms
22,400 KB
testcase_67 AC 364 ms
26,568 KB
testcase_68 AC 80 ms
22,428 KB
testcase_69 AC 372 ms
26,568 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <cassert>
#include <iostream>
#include <limits>
#include <vector>
#include <unordered_set>
#include <utility>
using namespace std;


template<size_t Mod, size_t Base>
struct RollingHash {
    static const size_t MAX_S = 1'100'000;
    vector<size_t> bases;
    RollingHash() : bases(MAX_S) {
        static_assert(Mod > Base &&
                      Mod % Base != 0 &&
                      numeric_limits<size_t>::max() / Mod > Mod);
        bases[0] = 1;
        for(size_t i = 1; i < MAX_S; i++) {
            bases[i] = bases[i-1] * Base % Mod;
        }
    }
    size_t getHash(const string &s) {
        assert(s.size() < MAX_S);
        size_t res = 0;
        for(size_t i = 0; i < s.size(); i++) {
            res = (res + bases[i] * s[i]) % Mod;
        }
        return res;
    }
    vector<size_t> getSwapHash(const string &s) {
        vector<size_t> head(s.size() + 1),
                       tail(s.size() + 1);
        for(size_t i = 0; i < s.size(); i++) {
            head[i+1] = (head[i  ] + bases[i] * s[i]) % Mod;
            auto j = s.size() - i - 1;
            tail[j  ] = (tail[j+1] + bases[j] * s[j]) % Mod;
        }
        vector<size_t> res(s.size() - 1);
        for(size_t i = 0; i < s.size() - 1; i++) {
            res[i] = (head[i] + tail[i+2] + bases[i] * s[i+1] + bases[i+1] * s[i]) % Mod;
        }
        return res;
    }
};

int main() {
    size_t n; cin >> n;
    vector<string> s(n);
    for(auto &i : s) cin >> i;
    RollingHash<1000000403, 442439> rh1;
    RollingHash<2000000579, 28468277> rh2;
    vector<bool> ans(n);
    unordered_set<size_t> st1;
    unordered_set<size_t> st2;
    for(size_t i = 0; i < n; i++) {
        auto h1 = rh1.getHash(s[i]);
        auto h2 = rh2.getHash(s[i]);
        auto v1 = rh1.getSwapHash(s[i]);
        auto v2 = rh2.getSwapHash(s[i]);
        bool exist = st1.count(h1) && st2.count(h2);
        for(size_t j = 0; j < s[i].size() - 1; j++) {
            exist = exist || (st1.count(v1[j]) && st2.count(v2[j]));
        }
        ans[i] = exist;
        st1.insert(h1);
        st2.insert(h2);
    }
    for(auto &&i : ans) cout << ((i) ? "Yes" : "No") << endl;
}
0