結果
| 問題 |
No.2254 Reverse Only
|
| コンテスト | |
| ユーザー |
 CoCo_Japan_pan
|
| 提出日時 | 2023-03-25 15:58:27 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 75 ms / 2,000 ms |
| コード長 | 6,688 bytes |
| コンパイル時間 | 2,040 ms |
| コンパイル使用メモリ | 205,844 KB |
| 最終ジャッジ日時 | 2025-02-11 18:04:32 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 47 |
ソースコード
#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";
}