結果
| 問題 | No.2210 equence Squence Seuence |
| ユーザー |
 k1suxu
|
| 提出日時 | 2023-02-10 23:25:20 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 522 ms / 2,000 ms |
| コード長 | 5,467 bytes |
| コンパイル時間 | 3,541 ms |
| コンパイル使用メモリ | 260,304 KB |
| 実行使用メモリ | 8,052 KB |
| 最終ジャッジ日時 | 2024-07-07 17:22:34 |
| 合計ジャッジ時間 | 8,708 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 25 |
ソースコード
// #pragma GCC target("avx")// #pragma GCC optimize("O3")// #pragma GCC optimize("unroll-loops")#include <bits/stdc++.h>using namespace std;#define rep(i,n) for(int i = 0; i < (int)n; i++)#define FOR(n) for(int i = 0; i < (int)n; i++)#define repi(i,a,b) for(int i = (int)a; i < (int)b; i++)#define all(x) x.begin(),x.end()//#define mp make_pair#define vi vector<int>#define vvi vector<vi>#define vvvi vector<vvi>#define vvvvi vector<vvvi>#define pii pair<int,int>#define vpii vector<pair<int,int>>template<typename T>void chmax(T &a, const T &b) {a = (a > b? a : b);}template<typename T>void chmin(T &a, const T &b) {a = (a < b? a : b);}using ll = long long;using ld = long double;const ll INF = numeric_limits<long long>::max() / 2;const ld pi = 3.1415926535897932384626433832795028;const ll mod = 998244353;int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};int dy[] = {0, -1, 0, 1, -1, 1, -1, 1};using ull = unsigned long long;struct Rolling_Hash {static const unsigned long long rh_mod = (1ull << 61ull) - 1;vector<unsigned long long> power;unsigned long long base;static inline unsigned long long add(unsigned long long a, unsigned long long b) {if((a += b) >= rh_mod) a -= rh_mod;return a;}static inline unsigned long long mul(unsigned long long a, unsigned long long b) {__uint128_t c = (__uint128_t) a * b;return add(c >> 61, c & rh_mod);}static inline unsigned long long generate_base() {mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());uniform_int_distribution< unsigned long long > rand(1, Rolling_Hash::rh_mod - 1);return rand(mt);}inline void expand(size_t sz) {if((int)power.size() < (int)sz + 1) {int pre_sz = (int) power.size();power.resize(sz + 1);for(int i = pre_sz - 1; i < (int)sz; i++) {power[i + 1] = mul(power[i], base);}}}Rolling_Hash() {base = generate_base();power = {1};}vector<unsigned long long> make_hash(const string &s) const {int sz = s.size();vector<unsigned long long> hashed(sz + 1);for(int i = 0; i < (int)sz; i++) {hashed[i + 1] = add(mul(hashed[i], base), s[i]);}return hashed;}template<typename T>vector<unsigned long long> make_hash(const vector<T> &s) const {int sz = s.size();vector<unsigned long long> hashed(sz + 1);for(int i = 0; i < (int)sz; i++) {hashed[i + 1] = add(mul(hashed[i], base), s[i]);}return hashed;}vector<unsigned long long> make_hash_string(const string &s) const {vector<char> ss;for(char c : s) ss.push_back(c);return make_hash<char>(ss);}unsigned long long query(const vector<unsigned long long> &s, int l, int r) {expand(r - l);return add(s[r], rh_mod - mul(s[l], power[r - l]));}unsigned long long combine(unsigned long long h1, unsigned long long h2, size_t h2len) {expand(h2len);return add(mul(h1, power[h2len]), h2);}int lcp(const vector<unsigned long long> &a, int l1, int r1, const vector<unsigned long long> &b, int l2, int r2) {int len = min(r1 - l1, r2 - l2);int low = 0, high = len + 1;while(high - low > 1) {int mid = (low + high) / 2;if(query(a, l1, l1 + mid) == query(b, l2, l2 + mid)) low = mid;else high = mid;}return low;}bool issame(const vector<unsigned long long> &a, int l1, int r1, const vector<unsigned long long> &b, int l2, int r2) {assert(r1-l1 == r2-l2);return query(a, l1, r1) == query(b, l2, r2);}bool issame(const vector<unsigned long long> &a, int l1, const vector<unsigned long long> &b, int l2, int len) {return issame(a, l1, l1+len, b, l2, l2+len);}template<typename T>int greater(const vector<T> &raw, const vector<unsigned long long> &hash, int l1, int r1, int l2, int r2) {// repi(i, l1, r1) cout << raw[i]; cout << " ";// repi(i, l2, r2) cout << raw[i]; cout << "\n";int LCP = lcp(hash, l1, r1, hash, l2, r2);if(LCP == min(r1 - l1, r2 - l2)) return 2;//same//0: l1の方がでかい, 1: l2の方がでかいreturn raw[l1+LCP] < raw[l2+LCP];}};//make function that can combine two hash tables//combine_hashes(vull l, vull r) -> return vull l+r (hash addition)void solve() {Rolling_Hash rh;int n, k;cin >> n >> k;vi s(n);FOR(n) cin >> s[i];vector<ull> hash = rh.make_hash<int>(s);vector<int> ans(n);iota(all(ans), 0);sort(all(ans), [&](int i, int j) {int now;// cout << i << " " << j << endl;if(i < j) {now = rh.greater<int>(s, hash, i+1, j+1, i, j);}else {now = rh.greater<int>(s, hash, j, i, j+1, i+1);}// cout << now << endl;if(now == 2) {return false;}if(now == 1) {return true;}if(now == 0) {return false;}assert(false);return false;});FOR(n) if(i != ans[k-1]) cout << s[i] << " "; cout << "\n";}signed main() {cin.tie(nullptr);ios::sync_with_stdio(false);solve();return 0;}