oj.uz

Submission #928855

# Submission time Handle Problem Language Result Execution time Memory
928855 2024-02-17T06:57:36 Z Muhammad_Aneeq Necklace (Subtask 1-3) (BOI19_necklace1) C++17
45 / 85
 1500 ms 648 KB 
/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/
 
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
#define int long long
int mod=1e9+7;
int power(int x,int y)
{
  int res=1;
  while (y)
  {
    if (y&1)
      res=(res*x)%mod;
    x=(x*x)%mod;
    y>>=1;
  }
  return res;
}
string x,y;
bool check(int i,int j,int k)
{
  string a,b;
  for (int l=i;l<i+k;l++)
    a+=x[l];
  for (int l=j;l<j+k;l++)
    b+=y[l];
  reverse(begin(a),end(a));
  for (int i=0;i<b.size();i++)
  {
    char g=b.back();
    b.pop_back();
    b=g+b;
    if (b==a)
      return 1;
  }
  reverse(begin(b),end(b));
  for (int i=0;i<b.size();i++)
  {
    char g=b.back();
    b.pop_back();
    b=g+b;
    if (b==a)
      return 1;    
  }
  return 0;
}
vector<int>pr={2,3,5,7,11,13,17,19,23,29,31,37,41,43,53,59,61,67,71,73,79,83,89,97,101};
inline void solve()
{
  cin>>x>>y;
  int n=x.size(),m=y.size();
  int hash[n+1]={};
  int hash1[m+1]={};
  hash[0]=hash1[0]=1;
  for (int i=0;i<n;i++)
    hash[i+1]=(hash[i]*pr[x[i]-'a'])%mod;
  for (int i=0;i<m;i++)
    hash1[i+1]=(hash1[i]*pr[y[i]-'a'])%mod;
  int ans=0,l,r;
  for (int k=1;k<=min(n,m);k++)
  {
    map<int,vector<int>>d;
    for (int i=0;i<=n-k;i++)
    {
      int z=(hash[i+k]*power(hash[i],mod-2))%mod;
      d[z].push_back(i);
    }
    for (int j=0;j<=m-k;j++)
    {
        int z=(hash1[j+k]*power(hash1[j],mod-2))%mod;
        if (d.find(z)!=d.end())
        {
          if (ans<k)
          {
            if (check(d[z][0],j,k))
            {
              ans=k;
              l=d[z][0],r=j;
              break;
            }
          }
        }
    }
  }
  cout<<ans<<endl;
  cout<<l<<' '<<r<<endl;
}
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);   
        solve();
}

Compilation message

necklace.cpp: In function 'bool check(long long int, long long int, long long int)':
necklace.cpp:35:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for (int i=0;i<b.size();i++)
      |                ~^~~~~~~~~
necklace.cpp:44:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for (int i=0;i<b.size();i++)
      |                ~^~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 11 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 11 ms 348 KB Output is correct
6 Correct 43 ms 472 KB Output is correct
7 Correct 44 ms 348 KB Output is correct
8 Correct 68 ms 444 KB Output is correct
9 Correct 56 ms 460 KB Output is correct
10 Correct 110 ms 348 KB Output is correct
11 Correct 210 ms 344 KB Output is correct
12 Correct 317 ms 460 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 11 ms 348 KB Output is correct
6 Correct 43 ms 472 KB Output is correct
7 Correct 44 ms 348 KB Output is correct
8 Correct 68 ms 444 KB Output is correct
9 Correct 56 ms 460 KB Output is correct
10 Correct 110 ms 348 KB Output is correct
11 Correct 210 ms 344 KB Output is correct
12 Correct 317 ms 460 KB Output is correct
13 Execution timed out 1528 ms 648 KB Time limit exceeded
14 Halted 0 ms 0 KB -