結果

問題 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  
実行時間 522 ms / 3,000 ms
コード長 2,162 bytes
コンパイル時間 1,165 ms
コンパイル使用メモリ 98,332 KB
実行使用メモリ 52,692 KB
最終ジャッジ日時 2024-06-02 06:33:39
合計ジャッジ時間 27,297 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 16 ms
20,352 KB
testcase_01 AC 16 ms
20,352 KB
testcase_02 AC 319 ms
33,700 KB
testcase_03 AC 343 ms
35,012 KB
testcase_04 AC 339 ms
34,196 KB
testcase_05 AC 296 ms
29,676 KB
testcase_06 AC 364 ms
34,504 KB
testcase_07 AC 183 ms
28,192 KB
testcase_08 AC 184 ms
24,412 KB
testcase_09 AC 268 ms
32,836 KB
testcase_10 AC 203 ms
26,496 KB
testcase_11 AC 132 ms
26,376 KB
testcase_12 AC 260 ms
30,356 KB
testcase_13 AC 351 ms
35,512 KB
testcase_14 AC 312 ms
30,812 KB
testcase_15 AC 411 ms
35,340 KB
testcase_16 AC 454 ms
38,824 KB
testcase_17 AC 140 ms
26,672 KB
testcase_18 AC 240 ms
29,712 KB
testcase_19 AC 223 ms
28,524 KB
testcase_20 AC 361 ms
36,336 KB
testcase_21 AC 301 ms
27,264 KB
testcase_22 AC 474 ms
39,900 KB
testcase_23 AC 464 ms
39,764 KB
testcase_24 AC 474 ms
39,772 KB
testcase_25 AC 474 ms
39,772 KB
testcase_26 AC 470 ms
39,772 KB
testcase_27 AC 486 ms
39,772 KB
testcase_28 AC 475 ms
39,776 KB
testcase_29 AC 471 ms
39,764 KB
testcase_30 AC 477 ms
39,764 KB
testcase_31 AC 482 ms
39,768 KB
testcase_32 AC 465 ms
39,772 KB
testcase_33 AC 477 ms
39,772 KB
testcase_34 AC 481 ms
39,772 KB
testcase_35 AC 486 ms
39,892 KB
testcase_36 AC 477 ms
39,768 KB
testcase_37 AC 475 ms
39,776 KB
testcase_38 AC 471 ms
39,772 KB
testcase_39 AC 484 ms
39,764 KB
testcase_40 AC 459 ms
39,768 KB
testcase_41 AC 483 ms
39,772 KB
testcase_42 AC 315 ms
33,524 KB
testcase_43 AC 311 ms
33,528 KB
testcase_44 AC 314 ms
33,532 KB
testcase_45 AC 309 ms
33,656 KB
testcase_46 AC 310 ms
33,588 KB
testcase_47 AC 224 ms
28,060 KB
testcase_48 AC 225 ms
28,060 KB
testcase_49 AC 218 ms
28,064 KB
testcase_50 AC 221 ms
27,988 KB
testcase_51 AC 220 ms
28,060 KB
testcase_52 AC 101 ms
52,692 KB
testcase_53 AC 103 ms
52,560 KB
testcase_54 AC 104 ms
52,688 KB
testcase_55 AC 100 ms
22,400 KB
testcase_56 AC 97 ms
22,400 KB
testcase_57 AC 99 ms
22,400 KB
testcase_58 AC 97 ms
37,072 KB
testcase_59 AC 522 ms
44,584 KB
testcase_60 AC 197 ms
23,808 KB
testcase_61 AC 102 ms
22,400 KB
testcase_62 AC 35 ms
20,992 KB
testcase_63 AC 139 ms
24,448 KB
testcase_64 AC 140 ms
24,320 KB
testcase_65 AC 141 ms
24,448 KB
testcase_66 AC 95 ms
22,400 KB
testcase_67 AC 356 ms
26,752 KB
testcase_68 AC 82 ms
22,400 KB
testcase_69 AC 347 ms
26,624 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