#853083 (C++17) No.2254 Reverse Only

• 問題: No.2254 Reverse Only
• ユーザー: CoCo_Japan_pan
• 提出日時: 2023-03-25 15:58:27
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 73 ms / 2,000 ms
• コード長: 6,688 bytes
• コンパイル時間: 2,164 ms
• コンパイル使用メモリ: 212,508 KB
• 実行使用メモリ: 6,528 KB
• 最終ジャッジ日時: 2024-09-18 22:26:10
• 合計ジャッジ時間: 5,490 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	1 ms; 5,376 KB
testcase_05	AC	1 ms; 5,376 KB
testcase_06	AC	1 ms; 5,376 KB
testcase_07	AC	1 ms; 5,376 KB
testcase_08	AC	64 ms; 6,272 KB
testcase_09	AC	72 ms; 6,400 KB
testcase_10	AC	41 ms; 6,400 KB
testcase_11	AC	73 ms; 6,272 KB
testcase_12	AC	64 ms; 6,272 KB
testcase_13	AC	65 ms; 6,272 KB
testcase_14	AC	65 ms; 6,272 KB
testcase_15	AC	66 ms; 6,400 KB
testcase_16	AC	69 ms; 6,528 KB
testcase_17	AC	69 ms; 6,276 KB
testcase_18	AC	66 ms; 6,400 KB
testcase_19	AC	53 ms; 6,272 KB
testcase_20	AC	61 ms; 6,404 KB
testcase_21	AC	67 ms; 6,272 KB
testcase_22	AC	39 ms; 6,400 KB
testcase_23	AC	53 ms; 6,404 KB
testcase_24	AC	42 ms; 6,528 KB
testcase_25	AC	43 ms; 6,528 KB
testcase_26	AC	45 ms; 6,400 KB
testcase_27	AC	4 ms; 5,376 KB
testcase_28	AC	14 ms; 5,376 KB
testcase_29	AC	30 ms; 5,376 KB
testcase_30	AC	26 ms; 5,376 KB
testcase_31	AC	15 ms; 5,376 KB
testcase_32	AC	17 ms; 5,376 KB
testcase_33	AC	9 ms; 5,376 KB
testcase_34	AC	40 ms; 5,376 KB
testcase_35	AC	26 ms; 5,376 KB
testcase_36	AC	54 ms; 5,888 KB
testcase_37	AC	57 ms; 6,016 KB
testcase_38	AC	12 ms; 5,376 KB
testcase_39	AC	51 ms; 5,632 KB
testcase_40	AC	3 ms; 5,376 KB
testcase_41	AC	22 ms; 5,376 KB
testcase_42	AC	14 ms; 5,376 KB
testcase_43	AC	42 ms; 5,376 KB
testcase_44	AC	62 ms; 6,272 KB
testcase_45	AC	40 ms; 5,376 KB
testcase_46	AC	3 ms; 5,376 KB

ソースコード

#line 1 "main.cpp"
// 提出時にassertはオフ
#ifndef DEBUG
#ifndef NDEBUG
#define NDEBUG
#endif
#endif

#include <bits/stdc++.h>
#line 2 "/home/cocojapanpan/Procon_CPP/proconLibrary/lib/string/rollinghash.hpp"

#line 4 "/home/cocojapanpan/Procon_CPP/proconLibrary/lib/string/rollinghash.hpp"

struct rolhash_mod {
    using u128 = __uint128_t;
    using u64 = uint64_t;

   public:
    constexpr rolhash_mod(u64 x = 0) noexcept : value(calcMod(x)) {}

    constexpr u64 val() const noexcept { return value; }

    constexpr rolhash_mod &operator+=(const rolhash_mod &a) noexcept {
        if ((value += a.value) >= MOD) value -= MOD;
        return *this;
    }
    constexpr rolhash_mod &operator-=(const rolhash_mod &a) noexcept {
        *this += (MOD - a.value);
        return *this;
    }
    constexpr rolhash_mod &operator*=(const rolhash_mod &a) noexcept {
        u128 product = (u128)value * a.value;
        product = (product >> 61) + (product & MOD);
        if (product >= MOD) product -= MOD;
        value = product;
        return *this;
    }
    constexpr rolhash_mod operator+(const rolhash_mod &a) const noexcept {
        rolhash_mod cpy(*this);
        return cpy += a;
    }
    constexpr rolhash_mod operator-(const rolhash_mod &a) const noexcept {
        rolhash_mod cpy(*this);
        return cpy -= a;
    }
    constexpr rolhash_mod operator*(const rolhash_mod &a) const noexcept {
        rolhash_mod cpy(*this);
        return cpy *= a;
    }
    constexpr bool operator==(const rolhash_mod &a) const noexcept {
        return value == a.value;
    }
    constexpr bool operator!=(const rolhash_mod &a) const noexcept {
        return value != a.value;
    }

    // べき乗のmod(tableを用意せずその場でやってるのでlog(beki)かかる)
    constexpr static u64 power(u64 base, u64 beki) noexcept {
        rolhash_mod curbekiMod(base);
        rolhash_mod ret(1);
        while (beki > 0) {
            if (beki & 1) ret *= curbekiMod;
            curbekiMod *= curbekiMod;
            beki >>= 1;
        }
        return ret.val();
    }

   private:
    u64 value;  // 中で保持しておくmod
    constexpr static u64 MOD = (1ULL << 61) - 1;
    constexpr static u64 calcMod(const u64 &x) noexcept {
        u64 cur = x >> 61;
        if ((cur += (x & MOD)) >= MOD) cur -= MOD;
        return cur;
    }
};

// 部分文字列[l,r)のhash値を返すqueryを定数時間で
struct rolhash {
    using u64 = uint64_t;

   public:
    template <class T>
    explicit rolhash(const std::vector<T> &input) : base(genBase()), N(input.size()) {
        basebeki_table.resize(N + 1);
        basebeki_table[0] = 1;
        for (int i = 1; i <= N; i++) {
            basebeki_table[i] = basebeki_table[i - 1] * base;
        }
        front_table.resize(N + 1);
        for (int i = 1; i <= N; i++) {
            front_table[i] = front_table[i - 1] * base + input[i - 1];
        }
    }
    explicit rolhash(const std::string &input_string)
        : rolhash(std::vector<char>(input_string.begin(), input_string.end())) {
    }

    // 部分列[l,r)のhash値を返す l==rのときは0を返す
    rolhash_mod query(int l, int r) const {
        assert(l <= r);
        if (l == r) return rolhash_mod(0);
        return (front_table[r] - front_table[l] * basebeki_table[r - l]);
    }

    // baseのbeki乗を返す
    rolhash_mod get_basebeki(int beki) const {
        return basebeki_table[beki];
    }  // queryで足りないとき用

    // 部分列[0,i)のhash値を返す
    rolhash_mod get_front(int i) const {
        return front_table[i];
    }  // queryで足りないとき用

    // [2, MOD - 2]のbaseを乱数として生成
    static u64 genBase() {
        auto rand_time =
            std::chrono::duration_cast<std::chrono::nanoseconds>(
                std::chrono::high_resolution_clock::now().time_since_epoch())
                .count();               // 非決定的な乱数
        std::mt19937_64 mt(rand_time);  // メルセンヌ・ツイスタ 64bit
        std::uniform_int_distribution<u64> randbase(2ULL, MOD - 2);
        return randbase(mt);
    }

   private:
    constexpr static u64 MOD = (1ULL << 61) - 1;
    const u64 base;
    const int N;
    // baseの0乗からN乗を記録
    std::vector<rolhash_mod> basebeki_table;
    // [0,i)の部分列のhash値を記録
    std::vector<rolhash_mod> front_table;
};
#line 10 "main.cpp"
using namespace std;
using ll = long long;

#define ALL(x) (x).begin(), (x).end()
template <class T> using vec = vector<T>;

int N, k;

// 多重集合一致判定
bool isSameSet(const vec<int> &A_, const vec<int> &B_) {
    vec<int> A = A_, B = B_;
    if(A.size() != B.size()) {
        return false;
    }
    sort(ALL(A));
    sort(ALL(B));
    for(int i = 0; i < (int)A.size(); i++) {
        if(A[i] != B[i]) return false;
    }
    return true;
}

bool isTotallySame(const vec<int> &A, const vec<int> &B) {
    if(A.size() != B.size()) return false;
    for(int i = 0; i < (int)A.size(); i++) {
        if(A[i] != B[i]) return false;
    }
    return true;
}

bool solve(const vec<int> &A, const vec<int> &B) {
    if(!isSameSet(A, B)) return false;
    int size = A.size();
    if(k > N) {
        return isTotallySame(A, B);
    }
    if(k == N) {
        vec<int> rev_A = A;
        reverse(ALL(rev_A));
        return (isTotallySame(A, B) || isTotallySame(rev_A, B));
    }
    if(k == N - 1) {
        rolhash_mod base = rolhash::genBase();
        vec<rolhash_mod> bekiTable(size + 1, 1);
        for(int i = 1; i <= size; i++) {
            bekiTable[i] = bekiTable[i - 1] * base;
        }
        rolhash_mod A_hash, B_hash;
        for(int i = 0; i < size; i++) {
            A_hash += bekiTable[i] * A[i];
            B_hash += bekiTable[i] * B[i];
        }
        if(A_hash == B_hash) return true;
        for(int i = 1; i < size; i++) {
            A_hash = A_hash * base - (bekiTable[size] - 1) * A[size - i];
            if(A_hash == B_hash) return true;
        }
        rolhash_mod rev_A_hash;
        for(int i = 0; i < size; i++) {
            rev_A_hash += bekiTable[i] * A[size - 1 - i];
        }
        if(rev_A_hash == B_hash) return true;
        for(int i = 1; i < size; i++){
            rev_A_hash = rev_A_hash * base - (bekiTable[size] - 1) * A[i - 1];
            if(rev_A_hash == B_hash) return true;
        }
        return false;
    }
    // k <= N - 2
    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> k;
    vec<int> A(N), B(N);
    for(int &a : A) cin >> a;
    for(int &b : B) cin >> b;
    cout << (solve(A, B) ? "Yes" : "No") << "\n";
}