oj.uz

Submission #928887

# Submission time Handle Problem Language Result Execution time Memory
928887 2024-02-17T07:35:51 Z UmairAhmadMirza Necklace (Subtask 1-3) (BOI19_necklace1) C++17
9 / 85
 137 ms 8180 KB 
#include <iostream>
using namespace std;
#define int long long
int const N=405;
int const mod=5e9+7;
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=n-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 7000 KB Output is partially correct
2 Partially correct 3 ms 7004 KB Output is partially correct
3 Partially correct 3 ms 7000 KB Output is partially correct
4 Partially correct 3 ms 7004 KB Output is partially correct
5 Correct 3 ms 7000 KB Output is correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 7000 KB Output is partially correct
2 Partially correct 3 ms 7004 KB Output is partially correct
3 Partially correct 3 ms 7000 KB Output is partially correct
4 Partially correct 3 ms 7004 KB Output is partially correct
5 Correct 3 ms 7000 KB Output is correct
6 Partially correct 127 ms 8020 KB Output is partially correct
7 Partially correct 131 ms 8180 KB Output is partially correct
8 Partially correct 107 ms 7772 KB Output is partially correct
9 Partially correct 122 ms 8032 KB Output is partially correct
10 Partially correct 137 ms 8020 KB Output is partially correct
11 Correct 136 ms 7892 KB Output is correct
12 Partially correct 118 ms 7772 KB Output is partially correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 7000 KB Output is partially correct
2 Partially correct 3 ms 7004 KB Output is partially correct
3 Partially correct 3 ms 7000 KB Output is partially correct
4 Partially correct 3 ms 7004 KB Output is partially correct
5 Correct 3 ms 7000 KB Output is correct
6 Partially correct 127 ms 8020 KB Output is partially correct
7 Partially correct 131 ms 8180 KB Output is partially correct
8 Partially correct 107 ms 7772 KB Output is partially correct
9 Partially correct 122 ms 8032 KB Output is partially correct
10 Partially correct 137 ms 8020 KB Output is partially correct
11 Correct 136 ms 7892 KB Output is correct
12 Partially correct 118 ms 7772 KB Output is partially correct
13 Runtime error 10 ms 3164 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -