# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
290090 | alexandra_udristoiu | Necklace (Subtask 4) (BOI19_necklace4) | C++14 | 525 ms | 504 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<iostream>
#include<cstring>
using namespace std;
int n, m, i, j, sol, x, ii, jj, val, nr;
int d[3005], ds[3005], z[6005];
char a[3005], b[3005], s[6005];
void zet(){
int i, ii = 0;
for(i = 2; i <= nr; i++){
if(ii + z[ii] - 1 >= i){
z[i] = min(ii + z[ii] - i, z[i - ii + 1]);
}
else{
z[i] = 0;
}
while(i + z[i] <= nr && s[ z[i] + 1 ] == s[ i + z[i] ]){
z[i]++;
}
if(i + z[i] > ii + z[ii]){
ii = i;
}
}
}
void solve(int t){
for(i = 1; i <= n; i++){
nr = 0;
for(j = i; j <= n; j++){
s[++nr] = a[j];
}
s[++nr] = '*';
for(j = 1; j <= m; j++){
s[++nr] = b[j];
}
zet();
x = m;
for(j = nr; j >= nr - m + 1; j--){
d[x] = z[j];
x--;
}
nr = 0;
for(j = i - 1; j >= 1; j--){
s[++nr] = a[j];
}
s[++nr] = '*';
for(j = m; j >= 1; j--){
s[++nr] = b[j];
}
zet();
memset(ds, 0, sizeof(ds) );
x = m;
for(j = i + 1; j <= nr; j++){
ds[ x - z[j] + 1] = max(z[j], ds[ x - z[j] + 1 ]);
x--;
}
for(j = 1; j <= m; j++){
val = d[j] + ds[ j + d[j] ];
if(val > sol){
sol = val;
if(t == 0){
jj = j;
}
else{
jj = j + val - 1;
jj = m - jj + 1;
}
ii = i - ds[ j + d[j] ];
}
sol = max(sol, d[j] + ds[ j + d[j] ]);
}
}
}
int main(){
cin>> a + 1;
n = strlen(a + 1);
cin>> b + 1;
m = strlen(b + 1);
solve(0);
for(i = 1, j = m; i < j; i++, j--){
swap(b[i], b[j]);
}
solve(1);
cout<< sol <<"\n";
cout<< ii - 1 <<" "<< jj - 1 <<"\n";
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |