oj.uz

Submission #928876

# Submission time Handle Problem Language Result Execution time Memory
928876 2024-02-17T07:27:09 Z UmairAhmadMirza Necklace (Subtask 1-3) (BOI19_necklace1) C++17
9 / 85
 142 ms 8192 KB 
#include <iostream>
using namespace std;
#define int long long
int const N=405;
int const mod=1e14+1;
int const base=727;
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 5 ms 7004 KB Output is partially correct
2 Partially correct 3 ms 6860 KB Output is partially correct
3 Partially correct 3 ms 7004 KB Output is partially correct
4 Partially correct 3 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 5 ms 7004 KB Output is partially correct
2 Partially correct 3 ms 6860 KB Output is partially correct
3 Partially correct 3 ms 7004 KB Output is partially correct
4 Partially correct 3 ms 7004 KB Output is partially correct
5 Partially correct 3 ms 7004 KB Output is partially correct
6 Partially correct 142 ms 8192 KB Output is partially correct
7 Partially correct 128 ms 7932 KB Output is partially correct
8 Partially correct 102 ms 7816 KB Output is partially correct
9 Partially correct 125 ms 8016 KB Output is partially correct
10 Partially correct 136 ms 8072 KB Output is partially correct
11 Partially correct 131 ms 8020 KB Output is partially correct
12 Partially correct 116 ms 7768 KB Output is partially correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 7004 KB Output is partially correct
2 Partially correct 3 ms 6860 KB Output is partially correct
3 Partially correct 3 ms 7004 KB Output is partially correct
4 Partially correct 3 ms 7004 KB Output is partially correct
5 Partially correct 3 ms 7004 KB Output is partially correct
6 Partially correct 142 ms 8192 KB Output is partially correct
7 Partially correct 128 ms 7932 KB Output is partially correct
8 Partially correct 102 ms 7816 KB Output is partially correct
9 Partially correct 125 ms 8016 KB Output is partially correct
10 Partially correct 136 ms 8072 KB Output is partially correct
11 Partially correct 131 ms 8020 KB Output is partially correct
12 Partially correct 116 ms 7768 KB Output is partially correct
13 Runtime error 11 ms 3164 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -