oj.uz

Submission #928898

# Submission time Handle Problem Language Result Execution time Memory
928898 2024-02-17T07:47:48 Z UmairAhmadMirza Necklace (Subtask 1-3) (BOI19_necklace1) C++17
9 / 85
 140 ms 8096 KB 
#include <iostream>
using namespace std;
#define int long long
int const N=405;
int const mod=10000000007;
int const base=1e5+237;
int hsh1[N][N];
int hsh2[N][N];
int r_hsh1[N][N];
int r_hsh2[N][N];
int min_hsh1[N][N];
int min_hsh2[N][N];
// map<int,bool> mp1;
// map<int,bool> mp2;
int pw[N];
string a,b;
void make_hash1(){
  int n=a.length();
  for(int i=1;i<=n;i++){
    int h1=0;
    for(int j=i;j<=n;j++){
      h1*=base;
      h1%=mod;
      h1+=a[j-1];
      h1%=mod;
      hsh1[i][j]=h1;
    }
  }
  for(int i=n;i>=1;i--){
    int h1=0;
    for(int j=i;j>=1;j--){
      h1*=base;
      h1%=mod;
      h1+=a[j-1];
      h1%=mod;
      r_hsh1[j][i]=h1;
    }
  }
}
void make_hash2(){
  int n=b.length();
  for(int i=1;i<=n;i++){
    int h1=0;
    for(int j=i;j<=n;j++){
      h1*=base;
      h1%=mod;
      h1+=b[j-1];
      h1%=mod;
      hsh2[i][j]=h1;
    }
  }
  for(int i=n;i>=1;i--){
    int h1=0;
    for(int j=i;j>=1;j--){
      h1*=base;
      h1%=mod;
      h1+=b[j-1];
      h1%=mod;
      r_hsh2[j][i]=h1;
    }
  }
}
void set_hsh1(){
  int n=a.length();
  int h=0;
  for(int i=1;i<=n;i++)
    for(int j=i;j<=n;j++){
      min_hsh1[i][j]=hsh1[i][j];
      for(int k=i;k<=j;k++){
        h=(hsh1[k][j]*pw[k-i])%mod;
        h+=hsh1[i][k-1];
        h%=mod;
        min_hsh1[i][j]=min(min_hsh1[i][j],h);
      }
      // cout<<i<<' '<<j<<' '<<min_hsh1[i][j]<<endl;
    }
  
  for(int i=1;i<=n;i++)
    for(int j=i;j<=n;j++){
      // min_hsh1[i][j]=hsh2[i][j];
      for(int k=i;k<=j;k++){
        h=(r_hsh1[i][k]*pw[j-k])%mod;
        h+=r_hsh1[k+1][j];
        h%=mod;
        min_hsh1[i][j]=min(min_hsh1[i][j],h);
      }
      // cout<<i<<' '<<j<<' '<<min_hsh1[i][j]<<endl;
    }
}
void set_hsh2(){
  int n=b.length();
  int h=0;
  for(int i=1;i<=n;i++)
    for(int j=i;j<=n;j++){
      min_hsh2[i][j]=hsh2[i][j];
      for(int k=i;k<=j;k++){
        h=(hsh2[k][j]*pw[k-i])%mod;
        h+=hsh2[i][k-1];
        h%=mod;
        min_hsh2[i][j]=min(min_hsh2[i][j],h);
      }
      // cout<<i<<' '<<j<<' '<<min_hsh2[i][j]<<endl;
    }
  
  for(int i=1;i<=n;i++)
    for(int j=i;j<=n;j++){
      for(int k=i;k<=j;k++){
        h=(r_hsh2[i][k]*pw[j-k])%mod;
        h+=r_hsh2[k+1][j];
        h%=mod;
        min_hsh2[i][j]=min(min_hsh2[i][j],h);
      }
      // cout<<i<<' '<<j<<' '<<min_hsh2[i][j]<<endl;
    }
}
void pwer(){
  pw[0]=1;
  for(int i=1;i<N;i++)
    pw[i]=(pw[i-1]*base)%mod;
}

signed main() 
{
  cin>>a>>b;
  pwer();
  make_hash1();
  make_hash2();
  set_hsh1();
  set_hsh2();
  int n=a.length();
  int m=b.length();
  for(int l=min(n,m)-1;l>=0;l--)
    for(int i=1;i<=(n-l);i++)
      for(int j=1;j<=m-l;j++){
        if(min_hsh1[i][i+l]==min_hsh2[j][j+l]){
          cout<<l+1<<endl;
          cout<<i-1<<' '<<j-1<<endl;
          return 0;
        }
      }
}

Subtask #1
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 7004 KB Output is partially correct
2 Partially correct 4 ms 7192 KB Output is partially correct
3 Partially correct 3 ms 7004 KB Output is partially correct
4 Partially correct 4 ms 7004 KB Output is partially correct
5 Partially correct 3 ms 7004 KB Output is partially correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 7004 KB Output is partially correct
2 Partially correct 4 ms 7192 KB Output is partially correct
3 Partially correct 3 ms 7004 KB Output is partially correct
4 Partially correct 4 ms 7004 KB Output is partially correct
5 Partially correct 3 ms 7004 KB Output is partially correct
6 Partially correct 127 ms 8096 KB Output is partially correct
7 Partially correct 127 ms 7940 KB Output is partially correct
8 Partially correct 102 ms 7772 KB Output is partially correct
9 Partially correct 130 ms 7864 KB Output is partially correct
10 Partially correct 134 ms 8020 KB Output is partially correct
11 Partially correct 140 ms 7896 KB Output is partially correct
12 Partially correct 118 ms 7768 KB Output is partially correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 7004 KB Output is partially correct
2 Partially correct 4 ms 7192 KB Output is partially correct
3 Partially correct 3 ms 7004 KB Output is partially correct
4 Partially correct 4 ms 7004 KB Output is partially correct
5 Partially correct 3 ms 7004 KB Output is partially correct
6 Partially correct 127 ms 8096 KB Output is partially correct
7 Partially correct 127 ms 7940 KB Output is partially correct
8 Partially correct 102 ms 7772 KB Output is partially correct
9 Partially correct 130 ms 7864 KB Output is partially correct
10 Partially correct 134 ms 8020 KB Output is partially correct
11 Partially correct 140 ms 7896 KB Output is partially correct
12 Partially correct 118 ms 7768 KB Output is partially correct
13 Runtime error 11 ms 3160 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -