#1182029 (C++23(gcc16)) No.3673 未来予知

• 問題: No.3673 未来予知
• ユーザー: harurun
• 提出日時: 2026-09-02 03:22:52
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 4,358 bytes
• コンパイル時間: 4,756 ms
• コンパイル使用メモリ: 507,604 KB
• 実行使用メモリ: 9,764 KB
• 最終ジャッジ日時: 2026-09-04 23:08:58
• 合計ジャッジ時間: 12,531 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge3_0

ファイルパターン	結果
sample	AC * 2 TLE * 1
other	AC * 19 TLE * 13

ソースコード

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <immintrin.h>

using namespace std;

inline static int encode(char c){
    switch(c){
        case 'R': return 0;
        case 'S': return 1;
        case 'P': return 2;
        case 'X': return 3;
        default: return -1;
    }
}

int expecteddd[100];

const char s[] = "XRSP";

inline static uint32_t step32(uint32_t state){
    state ^= state << 13;
    state ^= state >> 17;
    state ^= state << 5;
    return state;
}

__attribute__((target("avx512f"), always_inline))
static inline __m512i step512(__m512i state){
    state = _mm512_xor_si512(
        state,
        _mm512_slli_epi32(state, 13)
    );

    state = _mm512_xor_si512(
        state,
        _mm512_srli_epi32(state, 17)
    );

    state = _mm512_xor_si512(
        state,
        _mm512_slli_epi32(state, 5)
    );

    return state;
}

__attribute__((target("avx512f")))
uint32_t find_initial_state(){
    const __m512i offsets = _mm512_setr_epi32(
        0, 1, 2, 3,
        4, 5, 6, 7,
        8, 9, 10, 11,
        12, 13, 14, 15
    );

    const __m512i mask3 = _mm512_set1_epi32(3);
    const __m512i expected0 = _mm512_set1_epi32(expecteddd[0]);

    /*
        initial_state = x とする。

        xorshift を1回行った後の下位2bitは

        bit 0 = x[0] ^ x[4] ^ x[17]
        bit 1 = x[1] ^ x[5] ^ x[18]

        となる。

        h = x >> 2 とすると、
        expecteddd[0] を満たす下位2bitは

        low = (expecteddd[0] ^ (h >> 2) ^ (h >> 15)) & 3

        で一意に決定できる。

        したがって 2^32 個全部を見る必要はなく、
        h の 2^30 通りだけ調べればよい。
    */

    constexpr uint32_t LIMIT = uint32_t{1} << 30;

    for(uint32_t base = 0; base < LIMIT; base += 16){
        __m512i h = _mm512_add_epi32(
            _mm512_set1_epi32(base),
            offsets
        );

        /*
            expecteddd[0] を満たす
            initial_state の下位2bitを直接作る。
        */
        __m512i low = _mm512_xor_si512(
            _mm512_srli_epi32(h, 2),
            _mm512_srli_epi32(h, 15)
        );

        low = _mm512_xor_si512(low, expected0);
        low = _mm512_and_si512(low, mask3);

        __m512i state = _mm512_or_si512(
            _mm512_slli_epi32(h, 2),
            low
        );

        /*
            expecteddd[0] は必ず一致するので比較不要。
            ただし state 自体は1回進める。
        */
        state = step512(state);

        __mmask16 active = 0xFFFF;

        for(int j = 1; j < 100; ++j){
            state = step512(state);

            __m512i r = _mm512_and_si512(
                state,
                mask3
            );

            /*
                active &= (r == expecteddd[j])

                をAVX-512のmasked compareで一度に行う。
            */
            active = _mm512_mask_cmpeq_epi32_mask(
                active,
                r,
                _mm512_set1_epi32(expecteddd[j])
            );

            if(active == 0){
                break;
            }
        }

        if(active != 0){
            unsigned lane =
                __builtin_ctz(static_cast<unsigned>(active));

            uint32_t h0 = base + lane;

            /*
                SIMD側と同じ式で initial_state を復元。
            */
            uint32_t low0 = (
                static_cast<uint32_t>(expecteddd[0])
                ^ (h0 >> 2)
                ^ (h0 >> 15)
            ) & 3u;

            return (h0 << 2) | low0;
        }
    }

    return 0;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string T;
    cin >> T;

    for(int j = 0; j < 100; ++j){
        expecteddd[j] = encode(T[j]);
    }

    uint32_t initial_state = find_initial_state();

    int N;
    cin >> N;

    uint32_t state = initial_state;

    /*
        T の100文字分まで進める。
    */
    for(int i = 0; i < 100; ++i){
        state = step32(state);
    }

    /*
        coutを1文字ずつ呼ばず、
        一旦stringに書き込む。
    */
    string ans(N, '\0');

    for(int i = 0; i < N; ++i){
        state = step32(state);
        ans[i] = s[state & 3];
    }

    cout << ans << '\n';

    return 0;
}