結果

問題 No.2102 [Cherry Alpha *] Conditional Reflection
コンテスト
ユーザー sapphire__15
提出日時 2022-08-13 02:55:12
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 629 ms / 3,000 ms
コード長 2,162 bytes
コンパイル時間 1,234 ms
コンパイル使用メモリ 93,104 KB
最終ジャッジ日時 2025-01-30 22:05:48
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 70
権限があれば一括ダウンロードができます

ソースコード

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