제출 #1005588

#제출 시각아이디문제언어결과실행 시간메모리
1005588anangoNecklace (Subtask 4) (BOI19_necklace4)C++17
0 / 15
1509 ms500 KiB
#include <bits/stdc++.h> #define int long long using namespace std; mt19937 rng; int INF = 1LL<<60; int p = 2071723; int MOD = 1000000033; std::chrono::steady_clock::time_point begin2 = std::chrono::steady_clock::now(); 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); } int cutoff; 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<40000000; trial++) { if (!(trial%1000)) { std::chrono::steady_clock::time_point end2 = std::chrono::steady_clock::now(); int x = std::chrono::duration_cast<std::chrono::microseconds>(end2 - begin2).count(); if (x>cutoff) { //cout <<x <<" " << cutoff <<" " << trial << " " << ans << endl; return {{ans,ans},xpos,ypos}; } } 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); const std::clock_t c_start = std::clock(); auto t_start = std::chrono::high_resolution_clock::now(); cin >> a; cin >> b; n=a.size(); m=b.size(); vector<pair<int,int>> ans2; vector<int> ans(3); int TL = 1470000; cutoff=TL/4; ans2=solve(); ans[0] = ans2[0].first; ans[1] = ans2[1].first; ans[2] = ans2[2].first; reverse(b.begin(), b.end()); cutoff=2*TL/4; 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()); cutoff=3*TL/4; 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()); cutoff=4*TL/4; 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 }

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

necklace.cpp: In function 'int main()':
necklace.cpp:136:24: warning: unused variable 'c_start' [-Wunused-variable]
  136 |     const std::clock_t c_start = std::clock();
      |                        ^~~~~~~
necklace.cpp:137:10: warning: variable 't_start' set but not used [-Wunused-but-set-variable]
  137 |     auto t_start = std::chrono::high_resolution_clock::now();
      |          ^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...