제출 #1005570

#제출 시각아이디문제언어결과실행 시간메모리
1005570anangoNecklace (Subtask 1-3) (BOI19_necklace1)C++17
53 / 85
1474 ms740 KiB
#include <bits/stdc++.h> #define int long long using namespace std; mt19937 rng; int INF = 1LL<<60; int p = 2071723; int MOD = 1000000033; string a; string b; int n,m; vector<int> hashes; void compute_hash(string s) { int n1 = s.size(); hashes.clear(); hashes=vector<int>(n1+1,0); int ha = 0; for (int i=0; i<n1; i++) { ha += s[i]-'a'; ha *= p; ha %= MOD; hashes[i+1] = ha; } } int exp(int p, int n) { int ans=1; int r = p; for (int i=0; i<30; i++) { if (n&(1<<i)) { ans*=r; ans%=MOD; } r*=r; r%=MOD; } return ans; } int gethash(int l, int r) { int h1 = hashes[l]; int h2 = hashes[r+1]; h1 *= exp(p,r-l+1); h1%=MOD; int dif = h2-h1; dif%=MOD; dif+=MOD; dif%=MOD; return dif; } bool check(int a, int b, int length) { return gethash(a,a+length-1)==gethash(b,b+length-1); } bool verify(int i, int j, int length) { //checks if i...i+length-1 in a = j...j+length-1 in b return gethash(i,length-1)==gethash(n+j, length-1); } vector<pair<int,int>> solve() { compute_hash(a+b); int ans = 0; pair<int,int> xpos; pair<int,int> ypos; for (int trial=0; trial*ans<6000000; trial++) { int i,j; i=rng()%n; j=rng()%m; if (a[i]!=b[j]) { continue; } int l,r; l=0; r=0; while (l+i>=0 && l+j>=0 && a[i+l]==b[j+l]) { //cout << "doing " << i <<" " << l <<" " << a[i+l] <<" " << b[j+l] << endl; l--; } l++; while (r+i<=n-1 && r+j<=m-1 && a[i+r]==b[j+r]) { r++; } r--; int length = r-l+1; int subans = length; if (subans>ans) { ans=subans; xpos={i+l,i+l+length}; ypos={j+l,j+l+length}; } if (subans<=ans/2) { continue; } for (int blubber=1; blubber<=length; blubber++) { //add it on both sides int la = i+r+1; int ra = i+r+blubber; int lb = j+l-blubber; int rb = j+l-1; if (!(0<=la && la<=n-1) || !(0<=lb && rb<=m-1)) { break; } if (gethash(la,ra)==gethash(n+lb,n+rb)) { int subans = blubber+length; if (subans>ans) { //cout << a <<" " << b <<" " << ans <<" " << i <<" " << j <<" " << blubber <<" " << subans << endl; //cout << la <<" " << ra <<" " << lb <<" " << rb << endl; ans=subans; xpos = {i+l,ra}; ypos = {lb,j+r}; } } } } return {{ans,ans},xpos,ypos}; } signed main() { //freopen("input.txt","r", stdin); //freopen("output.txt","w",stdout); cin >> a; cin >> b; n=a.size(); m=b.size(); vector<pair<int,int>> ans2; vector<int> ans(3); ans2=solve(); ans[0] = ans2[0].first; ans[1] = ans2[1].first; ans[2] = ans2[2].first; reverse(b.begin(), b.end()); ans2 = solve(); if (ans2[0].first>ans[0]) { ans[0] = ans2[0].first; ans[1] = ans2[1].first; ans[2] = m-ans2[2].second-1; } reverse(a.begin(), a.end()); ans2 = solve(); if (ans2[0].first>ans[0]) { ans[0] = ans2[0].first; ans[1] = n-ans2[1].second-1; ans[2] = m-ans2[2].second-1; } reverse(b.begin(), b.end()); ans2 = solve(); if (ans2[0].first>ans[0]) { ans[0] = ans2[0].first; ans[1] = n-ans2[1].second-1; ans[2] = ans2[2].first; } cout << ans[0] << endl; cout << ans[1] <<" " << ans[2] << endl; //want to store for each x and j, the smallest t such that match[x][t]+t = j }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...