Submission #530095

#TimeUsernameProblemLanguageResultExecution timeMemory
530095fatemetmhrNecklace (Subtask 1-3) (BOI19_necklace1)C++17
45 / 85
1591 ms460 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define pb push_back #define fi first #define se second #define all(x) x.begin(), x.end() const int maxn5 = 4e3 + 10; int n, m; //int mod[2] = {1000000007, 1000000009}; ll base[2] = {37, 31}; ll pw[2][maxn5]; ll has[4][2][maxn5]; vector <pair<int, int>> av, qu; inline ll get_hash(int ty, int id, int l, int r){ if(l == 0) return has[ty][id][r]; return (has[ty][id][r] - has[ty][id][l - 1] * pw[id][r - l + 1]); } inline int get_lim(int ty, int l){ if(ty == 0 || ty == 2) return n - l; return m - l; } inline bool same(int ty1, int l1, int ty2, int l2, int len){ //cout << ty1 << ' ' << l1 + len - 1 << ' ' << ty2 << ' ' << l2 + len - 1 << endl; /* if(ty1 == 0 && l1 + len - 1 >= n) return false; if(ty1 == 1 && l1 + len - 1 >= m) return false; if(ty1 == 2 && l1 + len - 1 >= n) return false; if(ty1 == 3 && l1 + len - 1 >= m) return false; if(ty2 == 0 && l2 + len - 1 >= n) return false; if(ty2 == 1 && l2 + len - 1 >= m) return false; if(ty2 == 2 && l2 + len - 1 >= n) return false; if(ty2 == 3 && l2 + len - 1 >= m) return false; //*/ if(get_hash(ty1, 0, l1, l1 + len - 1) != get_hash(ty2, 0, l2, l2 + len - 1)) return false; /* if(get_hash(ty1, 1, l1, l1 + len - 1) != get_hash(ty2, 1, l2, l2 + len - 1)) return false; */ return true; } inline int lcp(int ty1, int id1, int ty2, int id2){ int l = 0, r = min(get_lim(ty1, id1), get_lim(ty2, id2)) + 1; //cout << "here " << ty1 << ' ' << id1 << ' ' << ty2 << ' ' << id2 << ' ' << r << endl; while(r - l > 1){ int mid = (l + r) >> 1; if(same(ty1, id1, ty2, id2, mid)) l = mid; else r = mid; } return l; } inline pair<int, pair<int, int>> solve(string s, string t){ //cout << "wow! " << endl; n = s.size(); m = t.size(); string sp = s, tp = t; reverse(sp.begin(), sp.end()); reverse(tp.begin(), tp.end()); for(int j = 0; j < 1; j++){ pw[j][0] = 1; for(int i = 1; i < maxn5; i++) pw[j][i] = pw[j][i - 1] * base[j]; ll cur = 0; for(int i = 0; i < n; i++){ cur = (cur * base[j] + s[i] - 'a' + 1); has[0][j][i] = cur; } cur = 0; for(int i = 0; i < m; i++){ cur = (cur * base[j] + t[i] - 'a' + 1); has[1][j][i] = cur; } cur = 0; for(int i = 0; i < n; i++){ cur = (cur * base[j] + sp[i] - 'a' + 1); has[2][j][i] = cur; } cur = 0; for(int i = 0; i < m; i++){ cur = (cur * base[j] + tp[i] - 'a' + 1); has[3][j][i] = cur; } } int ans = 0, idt, ids; for(int i = 0; i < m; i++){ qu.clear(); av.clear(); for(int j = 0; j < n; j++){ int l = lcp(1, i, 0, j); qu.pb({l + j, j}); //cout << i << ' ' << j << ' ' << l << '\n'; l = i == 0 ? 0 : lcp(3, m - i, 2, n - j - 1); av.pb({j - l + 1, j}); //cout << i << ' ' << j << ' ' << l << '\n'; } sort(all(qu)); sort(all(av)); int ind = 0, mx = -1; for(auto [val, id] : qu){ while(ind < av.size() && av[ind].fi <= val){ mx = max(mx, av[ind].se); ind++; } if(mx - id + 1 >= ans && mx - id + 1 >= 1){ ans = mx - id + 1; ids = id; if(val - id >= ans) idt = i; else idt = i + val - id - 1 - (mx - id + 1) + 1; } } } return {ans, {ids, idt}}; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); string s, t; cin >> s >> t; pair <int, pair<int, int>> ans1 = solve(s, t); reverse(t.begin(), t.end()); pair <int, pair<int, int>> ans2 = solve(s, t); int len = ans2.fi, id = ans2.se.se; id = int(t.size()) - id - 1; id -= len - 1; ans2.se.se = id; if(ans1 < ans2) ans1 = ans2; cout << ans1.fi << '\n' << ans1.se.fi << ' ' << ans1.se.se << '\n'; }

Compilation message (stderr)

necklace.cpp: In function 'std::pair<int, std::pair<int, int> > solve(std::string, std::string)':
necklace.cpp:133:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |    while(ind < av.size() && av[ind].fi <= val){
      |          ~~~~^~~~~~~~~~~
necklace.cpp:148:25: warning: 'ids' may be used uninitialized in this function [-Wmaybe-uninitialized]
  148 |  return {ans, {ids, idt}};
      |                         ^
necklace.cpp:148:25: warning: 'idt' may be used uninitialized in this function [-Wmaybe-uninitialized]
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...