結果
問題 | No.2270 T0空間 |
ユーザー | k1suxu |
提出日時 | 2023-04-14 23:22:12 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 219 ms / 2,000 ms |
コード長 | 5,306 bytes |
コンパイル時間 | 3,353 ms |
コンパイル使用メモリ | 262,684 KB |
実行使用メモリ | 47,588 KB |
最終ジャッジ日時 | 2024-10-10 14:32:01 |
合計ジャッジ時間 | 7,287 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 3 ms
5,248 KB |
testcase_03 | AC | 3 ms
5,248 KB |
testcase_04 | AC | 3 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 3 ms
5,248 KB |
testcase_07 | AC | 4 ms
5,248 KB |
testcase_08 | AC | 3 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 3 ms
5,248 KB |
testcase_11 | AC | 39 ms
9,548 KB |
testcase_12 | AC | 23 ms
6,784 KB |
testcase_13 | AC | 64 ms
17,156 KB |
testcase_14 | AC | 53 ms
17,180 KB |
testcase_15 | AC | 55 ms
17,176 KB |
testcase_16 | AC | 104 ms
27,312 KB |
testcase_17 | AC | 219 ms
47,588 KB |
testcase_18 | AC | 207 ms
47,588 KB |
testcase_19 | AC | 200 ms
47,588 KB |
testcase_20 | AC | 201 ms
47,492 KB |
testcase_21 | AC | 208 ms
47,584 KB |
ソースコード
// #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; using ull = unsigned long long; 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}; #define int 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 compare(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]; } bool is_palindrome(const vector<unsigned long long> normal, const vector<unsigned long long> rev, int l, int r) { const int hash_len = (int)normal.size(); assert((int)rev.size() == hash_len); // cout << l << " " << r << " " << hash_len-r << " " << hash_len-l << endl; return issame(normal, l, r, rev, hash_len-1-r, hash_len-1-l); } }; void solve() { Rolling_Hash hasher; int n, m; cin >> n >> m; vector<string> s(m), t(n); FOR(m) { cin >> s[i]; rep(j, n) t[j].push_back(s[i][j]); } unordered_set<int> hashed; for(auto e : t) hashed.insert(hasher.make_hash_string(e).back()); cout << (hashed.size() == n? "Yes" : "No") << endl; } signed main() { cin.tie(nullptr); ios::sync_with_stdio(false); solve(); return 0; }