#808456 (C++14) No.2102 [Cherry Alpha *] Conditional Reflection

• 問題: No.2102 [Cherry Alpha *] Conditional Reflection
• ユーザー: 🍮かんプリン
• 提出日時: 2022-10-18 01:12:22
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 200 ms / 3,000 ms
• コード長: 3,161 bytes
• コンパイル時間: 1,719 ms
• コンパイル使用メモリ: 179,192 KB
• 実行使用メモリ: 19,876 KB
• 最終ジャッジ日時: 2023-09-10 22:32:02
• 合計ジャッジ時間: 14,500 ms
• ジャッジサーバーID （参考情報）: judge11 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,380 KB
testcase_01	AC	2 ms; 4,376 KB
testcase_02	AC	92 ms; 7,808 KB
testcase_03	AC	120 ms; 8,180 KB
testcase_04	AC	95 ms; 7,804 KB
testcase_05	AC	60 ms; 5,568 KB
testcase_06	AC	99 ms; 7,776 KB
testcase_07	AC	106 ms; 5,520 KB
testcase_08	AC	27 ms; 4,380 KB
testcase_09	AC	110 ms; 8,000 KB
testcase_10	AC	40 ms; 4,488 KB
testcase_11	AC	41 ms; 5,480 KB
testcase_12	AC	76 ms; 6,232 KB
testcase_13	AC	134 ms; 8,496 KB
testcase_14	AC	73 ms; 5,936 KB
testcase_15	AC	107 ms; 7,760 KB
testcase_16	AC	159 ms; 8,996 KB
testcase_17	AC	72 ms; 5,464 KB
testcase_18	AC	119 ms; 6,200 KB
testcase_19	AC	54 ms; 5,484 KB
testcase_20	AC	147 ms; 8,728 KB
testcase_21	AC	42 ms; 4,380 KB
testcase_22	AC	178 ms; 9,572 KB
testcase_23	AC	176 ms; 9,552 KB
testcase_24	AC	177 ms; 9,592 KB
testcase_25	AC	177 ms; 9,528 KB
testcase_26	AC	180 ms; 9,588 KB
testcase_27	AC	179 ms; 9,656 KB
testcase_28	AC	176 ms; 9,544 KB
testcase_29	AC	180 ms; 9,620 KB
testcase_30	AC	180 ms; 9,568 KB
testcase_31	AC	200 ms; 9,584 KB
testcase_32	AC	190 ms; 9,640 KB
testcase_33	AC	191 ms; 9,576 KB
testcase_34	AC	190 ms; 9,596 KB
testcase_35	AC	180 ms; 9,588 KB
testcase_36	AC	185 ms; 9,572 KB
testcase_37	AC	185 ms; 9,660 KB
testcase_38	AC	185 ms; 9,620 KB
testcase_39	AC	178 ms; 9,568 KB
testcase_40	AC	177 ms; 9,540 KB
testcase_41	AC	177 ms; 9,644 KB
testcase_42	AC	157 ms; 7,976 KB
testcase_43	AC	147 ms; 7,956 KB
testcase_44	AC	146 ms; 7,992 KB
testcase_45	AC	148 ms; 7,936 KB
testcase_46	AC	146 ms; 7,984 KB
testcase_47	AC	123 ms; 5,732 KB
testcase_48	AC	121 ms; 5,656 KB
testcase_49	AC	121 ms; 5,672 KB
testcase_50	AC	121 ms; 5,664 KB
testcase_51	AC	121 ms; 5,768 KB
testcase_52	AC	49 ms; 19,732 KB
testcase_53	AC	50 ms; 19,812 KB
testcase_54	AC	50 ms; 19,876 KB
testcase_55	AC	78 ms; 4,376 KB
testcase_56	AC	78 ms; 4,380 KB
testcase_57	AC	78 ms; 4,376 KB
testcase_58	AC	56 ms; 11,848 KB
testcase_59	AC	194 ms; 12,464 KB
testcase_60	AC	26 ms; 4,376 KB
testcase_61	AC	79 ms; 4,380 KB
testcase_62	AC	5 ms; 4,380 KB
testcase_63	AC	23 ms; 4,380 KB
testcase_64	AC	23 ms; 4,376 KB
testcase_65	AC	24 ms; 4,376 KB
testcase_66	AC	73 ms; 4,380 KB
testcase_67	AC	45 ms; 4,380 KB
testcase_68	AC	62 ms; 4,376 KB
testcase_69	AC	44 ms; 4,380 KB

ソースコード

/**
 *   @FileName	a.cpp
 *   @Author	kanpurin
 *   @Created	2022.10.18 01:09:55
**/

#include "bits/stdc++.h" 
using namespace std; 
typedef long long ll;

struct RollingHash {
private:
    using ull = unsigned long long;
    static const ull _mod = 0x1fffffffffffffff;
    static ull _base;
    vector<ull> _hashed, _power;

    inline ull _mul(ull a, ull b) const {
        ull au = a >> 31;
        ull ad = a & ((1UL << 31) - 1);
        ull bu = b >> 31;
        ull bd = b & ((1UL << 31) - 1);
        ull mid = ad * bu + au * bd;
        ull midu = mid >> 30;
        ull midd = mid & ((1UL << 30) - 1);
        ull ans = au * bu * 2 + midu + (midd << 31) + ad * bd;
        
        ans = (ans >> 61) + (ans & _mod);
        if (ans >= _mod) ans -= _mod;
        return ans;
    }
public:
    RollingHash(const string &s) {
        ll n = s.size();
        _hashed.assign(n + 1, 0);
        _power.assign(n + 1, 0);
        _power[0] = 1;
        for(ll i = 0; i < n; i++) {
            _power[i + 1] = _mul(_power[i], _base);
            _hashed[i + 1] = _mul(_hashed[i], _base) + s[i];
            if(_hashed[i + 1] >= _mod) _hashed[i + 1] -= _mod;
        }
    }
    
    ull get(ll l, ll r) const {
        ull ret = _hashed[r] + _mod - _mul(_hashed[l], _power[r - l]);
        if(ret >= _mod) ret -= _mod;
        return ret;
    }
    
    ull connect(ull h1, ull h2, ll h2len) const {
        ull ret = _mul(h1, _power[h2len]) + h2;
        if(ret >= _mod) ret -= _mod;
        return ret;
    }
    
    void connect(const string &s) {
        ll n = _hashed.size() - 1, m = s.size();
        _hashed.resize(n + m + 1);
        _power.resize(n + m + 1);
        for(ll i = n; i < n + m; i++) {
            _power[i + 1] = _mul(_power[i], _base);
            _hashed[i + 1] = _mul(_hashed[i], _base) + s[i - n];
            if(_hashed[i + 1] >= _mod) _hashed[i + 1] -= _mod;
        }
    }
    
    ll LCP(const RollingHash &b, ll l1, ll r1, ll l2, ll r2) const {
        ll len = min(r1 - l1, r2 - l2);
        ll low = -1, high = len + 1;
        while(high - low > 1) {
            ll mid = (low + high) / 2;
            if(get(l1, l1 + mid) == b.get(l2, l2 + mid)) low = mid;
            else high = mid;
        }
        return low;
    }
};

mt19937_64 mt{(unsigned int)time(NULL)};
RollingHash::ull RollingHash::_base = mt() % RollingHash::_mod;

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    int n;cin >> n;
    unordered_set<unsigned long long> st;
    for (int i = 0; i < n; i++) {
        string s;cin >> s;
        int m = s.size();
        RollingHash rh(s);
        bool yes = false;
        if (st.count(rh.get(0,m))) {
            puts("Yes");
            yes = true;
        }
        for (int j = 0; j <= m-2 && !yes; j++) {
            auto t = rh.connect(rh.get(0,j),rh.get(j+1,j+2),1);
            t = rh.connect(t,rh.get(j,j+1),1);
            t = rh.connect(t,rh.get(j+2,m),m-j-2);
            if (st.count(t)) {
                puts("Yes");
                yes = true;
            }
        }
        if (!yes) puts("No");
        st.insert(rh.get(0,m));
    }
    return 0;
}