結果

問題 No.2210 equence Squence Seuence
ユーザー 👑 emthrmemthrm
提出日時 2023-02-10 21:37:48
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,014 ms / 2,000 ms
コード長 3,333 bytes
コンパイル時間 3,358 ms
コンパイル使用メモリ 260,396 KB
実行使用メモリ 9,472 KB
最終ジャッジ日時 2024-07-07 15:48:48
合計ジャッジ時間 12,270 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr double EPS = 1e-8;
constexpr int MOD = 998244353;
// constexpr int MOD = 1000000007;
constexpr int DY4[]{1, 0, -1, 0}, DX4[]{0, -1, 0, 1};
constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1};
constexpr int DX8[]{0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U>
inline bool chmax(T& a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U>
inline bool chmin(T& a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
IOSetup() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
std::cout << fixed << setprecision(20);
}
} iosetup;
template <typename T = char>
struct RollingHash {
const std::int64_t base;
std::vector<T> str;
template <typename U>
explicit RollingHash(const U& str_, const std::int64_t base = generate_base())
: base(base), hashes({0}), powers({1}) {
const int n = str_.size();
str.reserve(n);
hashes.reserve(n + 1);
powers.reserve(n + 1);
for (const auto ch : str_) add(ch);
}
void add(const T ch) {
assert(0 <= ch && ch < MOD);
str.emplace_back(ch);
const std::int64_t h = mul(hashes.back(), base) + ch;
hashes.emplace_back(h >= MOD ? h - MOD : h);
const std::int64_t p = mul(powers.back(), base);
powers.emplace_back(p);
}
std::int64_t get(const int left, const int right) const {
const std::int64_t res =
hashes[right] - mul(hashes[left], powers[right - left]);
return res < 0 ? res + MOD : res;
}
private:
static constexpr int MOD_WIDTH = 61;
static constexpr std::int64_t MOD = (INT64_C(1) << MOD_WIDTH) - 1;
std::vector<std::int64_t> hashes, powers;
static std::int64_t generate_base() {
static std::mt19937_64 engine(std::random_device {} ());
static std::uniform_int_distribution<std::int64_t> dist(0, MOD - 1);
return dist(engine);
}
static std::int64_t mul(const std::int64_t a, const std::int64_t b) {
const std::int64_t au = a >> 31, ad = a & ((UINT32_C(1) << 31) - 1);
const std::int32_t bu = b >> 31, bd = b & ((UINT32_C(1) << 31) - 1);
const std::int64_t mid = au * bd + ad * bu;
std::int64_t res = au * bu * 2 + ad * bd + (mid >> 30)
+ ((mid & ((UINT32_C(1) << 30) - 1)) << 31);
res = (res >> MOD_WIDTH) + (res & MOD);
return res >= MOD ? res - MOD : res;
}
};
int main() {
int n, k; cin >> n >> k;
vector<int> a(n); REP(i, n) cin >> a[i];
RollingHash<int> hash(a);
vector<int> ans(n);
iota(ALL(ans), 0);
sort(ALL(ans), [&](const int l, const int r) -> bool {
const int x = min(l, r);
int lb = 0, ub = abs(r - l) + 1;
while (ub - lb > 1) {
const int mid = midpoint(lb, ub);
(hash.get(x, x + mid) == hash.get(x + 1, x + 1 + mid) ? lb : ub) = mid;
}
if (lb == abs(r - l)) return false;
return l < r ? a[l + 1 + lb] < a[l + lb] : a[r + lb] < a[r + 1 + lb];
});
// REP(i, n) cout << ans[i] << " \n"[i + 1 == n];
vector<int> b = a;
b.erase(next(b.begin(), ans[k - 1]));
REP(i, n - 1) cout << b[i] << " \n"[i + 1 == n - 1];
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0