제출 #866329

#제출 시각아이디문제언어결과실행 시간메모리
866329nikuradzeNecklace (Subtask 1-3) (BOI19_necklace1)C++14
0 / 85
1 ms348 KiB
/* Я русский, Я иду до конца. Я русский, Моя кровь от Отца. Я русский, И мне повезло. Я русский, Всему миру назло. Я русский! */ //#pragma GCC optimize("O3")' #pragma GCC optimize("Ofast") #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include <cstdio> #include <cmath> #include <set> #include <vector> #include <iostream> #include <algorithm> #include <map> using namespace std; #define double long double //#define int long long using ll = long long; const int mod = 1e9 + 7; const int mod9 = 1e9 + 9; const ll MAXN = 1e6 + 100; const int MAXB = 8; const int MAXL = 1e6 + 1e5; #ifndef ONLINE_JUDGE #define debug(x) cerr << (#x) << ": " << x << endl; #else #define debug(x) #endif int bin_pow(int x, int e) { int c = x, r = 1; for (; e; e >>= 1, c = c * 1LL * c % mod) { if (e & 1) r = r * 1LL * c % mod; } return r; } int rev(int a) { return bin_pow(a, mod - 2); } int make_add(int x, int y) { if ((ll)x + y >= mod) return x + y - mod; return x + y; } int mul(int x, int y) { ll p = (ll(x)) * y; return p % mod; } int gcd(int a, int b) { while (a > 0 && b > 0) { int c = a; a = b % a; b = c; } return a + b; } const int base = 61; struct hashes { vector<int> power; vector<int> pref; void init(string s, int m) { int n = s.size(); pref = vector<int>(n + 1); power = vector<int>(n + 1); power[0] = 1; for (int i = 0; i < n; i++) { pref[i + 1] = (pref[i] * base + s[i] - 96) % m; power[i + 1] = (power[i] * base) % m; } } int get(int i, int j, int m) { int ans = (pref[j] - (pref[i] * (power[j - i]) % m) + m) % m; return ans; } }; int get_st(string s, string t) { int n = s.size(), m = t.size(); set<pair<int, int> > all_hash_s; for (int i = 0; i < n; i++) { string add; for (int j = i; j < n; j++) { add += s[j]; string cadd = add; add = add + add; hashes m7, m9; m7.init(add, mod); m9.init(add, mod9); for (int p = 0; p < cadd.size(); p++) { int l = p, r = p + cadd.size(); int hash7 = m7.get(l, r, mod), hash9 = m9.get(l, r, mod9); all_hash_s.insert({ hash7, hash9 }); } add = cadd; } } int mx = 0; for (int i = 0; i < m; i++) { string add; for (int j = i; j < m; j++) { add += t[j]; string cadd = add; add = add + add; hashes m7, m9; m7.init(add, mod); m9.init(add, mod9); for (int p = 0; p < cadd.size(); p++) { int l = p, r = p + cadd.size(); int hash7 = m7.get(l, r, mod), hash9 = m9.get(l, r, mod9); if (all_hash_s.count({ hash7,hash9 })) { mx = max(mx, j - i + 1); break; } } add = cadd; } } return mx; } int stupid(string s, string t) { int mx1 = get_st(s, t); reverse(t.begin(), t.end()); int mx2 = get_st(s, t); return max(mx1, mx2); } vector<int> prefix_function(string s) { int n = (int)s.length(); vector<int> pi(n); for (int i = 1; i < n; ++i) { int j = pi[i - 1]; while (j > 0 && s[i] != s[j]) j = pi[j - 1]; if (s[i] == s[j]) ++j; pi[i] = j; } return pi; } int get(string s, string t) { int n = s.size(), m = t.size(); vector<vector<int> > pre_prefix_func; for (int i = 0; i <= m; i++) { string cur; for (int j = 0; j < n; j++) cur += s[j]; cur += '#'; for (int j = 0; j < i; j++) { cur += t[j]; } reverse(cur.begin(), cur.end()); vector<int> p = prefix_function(cur); pre_prefix_func.push_back(p); } int ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < 1; j++) { string to_ab; for (int p = i; p < n; p++) to_ab += s[p]; to_ab += '#'; for (int p = 0; p < m; p++) to_ab += t[p]; vector<int> ab = prefix_function(to_ab); int sz = ab.size(); int what_to_n = n - i; for (int p = what_to_n + 1; p < sz; p++) { int cur_add = ab[p]; //if (cur_add != p - what_to_n) continue; int ind = p - what_to_n - cur_add; int pos = cur_add + i + 1; pos = ind + 1 + n - pos; int may = pre_prefix_func[ind][pos]; ans = max(ans, may + cur_add); } } } return ans; } int clever(string s, string t) { int mx1 = get(s, t); reverse(t.begin(), t.end()); int mx2 = get(s, t); return max(mx1, mx2); } void solve() { string s, t; cin >> s >> t; int mx1 = get(s, t); reverse(t.begin(), t.end()); int mx2 = get(s, t); cout << max(mx1, mx2); } void gen() { string s, t; int n = rand() % 5 + 1, m = rand() % 5 + 1; for (int i = 0; i < n; i++) { int r = rand() % 3; s += (char)(r + 97); } for (int i = 0; i < m; i++) { int r = rand() % 3; t += (char)(r + 97); } int st = stupid(s, t); int cl = clever(s, t); if (st != cl) { cout << s << " " << t << endl; cout << st << " " << cl << endl; exit(0); } } int num = 0; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1 - 1 + 1; /* while (true) { debug(num++); gen(); } */ // cin >> t; while (t--) { solve(); } } /* acccb ccabc */

컴파일 시 표준 에러 (stderr) 메시지

necklace.cpp: In function 'int get_st(std::string, std::string)':
necklace.cpp:96:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |             for (int p = 0; p < cadd.size(); p++) {
      |                             ~~^~~~~~~~~~~~~
necklace.cpp:114:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |             for (int p = 0; p < cadd.size(); p++) {
      |                             ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...