제출 #524666

#제출 시각아이디문제언어결과실행 시간메모리
524666fcwNecklace (Subtask 4) (BOI19_necklace4)C++17
0 / 15
233 ms65540 KiB
#include <bits/stdc++.h> #define st first #define nd second using lint = int64_t; constexpr int MOD = int(1e9) + 7; constexpr int INF = 0x3f3f3f3f; constexpr int NINF = 0xcfcfcfcf; constexpr lint LINF = 0x3f3f3f3f3f3f3f3f; const long double PI = acosl(-1.0); // Returns -1 if a < b, 0 if a = b and 1 if a > b. int cmp_double(double a, double b = 0, double eps = 1e-9) { return a + eps > b ? b + eps > a ? 0 : 1 : -1; } using namespace std; vector<int> Z(const string& S) { vector<int> z(S.size()); int l = -1, r = -1; for(int i = 1; i < int(S.size()); ++i) { z[i] = i >= r ? 0 : min(r - i, z[i - l]); while (i + z[i] < int(S.size()) && S[i + z[i]] == S[z[i]]) z[i]++; if (i + z[i] > r) l = i, r = i + z[i]; } return z; } array<int, 3>solve(string s, string t){ array<int, 3>ans = {0, -1, -1}; int n = (int)s.size(), m = (int)t.size(); vector<int>z; vector<map<int, int>>w(n); for(int i=0;i<n;i++){ z = Z(s + t); for(int j=0;j<m;j++){ int d = min(z[n+j], n-i); if(d){ if(ans[0] < d) ans = {d, i, j}; int ni = i + d, nj = j + d; if(ni < n) w[ni][j] = max(w[ni][j], d); if(w[i].count(nj)){ int nd = w[i][nj]; if(ans[0] < d+nd) ans = {d+nd, i-nd, j}; } } } rotate(s.begin(), s.begin() + 1, s.end()); } return ans; } int main() { cin.tie(nullptr)->sync_with_stdio(false); string s, t; cin>>s>>t; int n = (int)s.size(), m = (int)t.size(); array<int, 3>ans = solve(s, t); reverse(t.begin(), t.end()); array<int, 3>rans = solve(s, t); if(ans[0] >= rans[0]){ cout<<ans[0]<<"\n"<<ans[1]<<" "<<ans[2]<<"\n"; } else{ cout<<rans[0]<<"\n"<<rans[1]<<" "<<m-(rans[2]+rans[0])<<"\n"; } return 0; } /* [ ]Leu o problema certo??? [ ]Ver se precisa de long long [ ]Viu o limite dos fors (é n? é m?) [ ]Tamanho do vetor, será que é 2e5 em vez de 1e5?? [ ]Testar sample [ ]Testar casos de borda [ ]1LL no 1LL << i [ ]Testar mod (é 1e9+7, mesmo?, será que o mod não ficou negativo?) */

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

necklace.cpp: In function 'int main()':
necklace.cpp:56:6: warning: unused variable 'n' [-Wunused-variable]
   56 |  int n = (int)s.size(), m = (int)t.size();
      |      ^
#Verdict Execution timeMemoryGrader output
Fetching results...