結果
問題 | No.2210 equence Squence Seuence |
ユーザー |
👑 ![]() |
提出日時 | 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 |
ソースコード
#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;}