Submission #853533

#	Time	Username	Problem	Language	Result	Execution time	Memory
853533		HoriaHaivas	Ispit (COCI19_ispit)	C++14	90 / 90	44 ms	3416 KiB

Main

/*
    "vrem gridiuri cu en si capa"
    - 2023 -
*/
#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")

using namespace std;

const int mod=1e9+7;
const int base=29;
char a[505][505];
int prefhash[505][505];
int suffhash[505][505];
bool compatibil[505][505];
int f[27][505];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int i,j,n,k,l,h;
    bool ok,ok2;
    cin >> n >> k;
    for (i=1; i<=n; i++)
    {
        for (j=1; j<=n; j++)
        {
            cin >> a[i][j];
        }
    }
    for (i=1; i<=n; i++)
    {
        for (j=1; j<=n; j++)
        {
            f[a[i][j]-'a'+1][i]++;
        }
    }
    for (j=1;j<=n;j++)
    {
         for (l=j+1;l<=n;l++)
         {
              ok=true;
              for (h=1;h<=26;h++)
              {
                   if (f[h][j]!=f[h][l])
                       ok=false;
              }
              if (ok==true)
              {
                  compatibil[j][l]=1;
                  compatibil[l][j]=1;
              }
         }
    }
    for (i=1;i<=n;i++)
    {
         prefhash[i][0]=1;
         for (j=1;j<=n;j++)
         {
              prefhash[i][j]=((prefhash[i][j-1]*base)%mod+(a[i][j]-'a'+1))%mod;
         }
         suffhash[i][n+1]=1;
         for (j=n;j>=1;j--)
         {
              suffhash[i][j]=((suffhash[i][j+1]*base)%mod+(a[i][j]-'a'+1))%mod;
         }
    }
    ok2=false;
    for (i=1;i<=n && !ok2;i++)
    {
         for (j=i+1;j<=n && !ok2;j++)
         {
              if (compatibil[i][j] || compatibil[j][i])
              {
                  for (l=1;l<=n-k+1 && !ok2;l++)
                  {
                       if (suffhash[i][l+k]==suffhash[j][l+k] && prefhash[i][l-1]==prefhash[j][l-1])
                           ok2=true;
                  }
              }
         }
    }
    if (ok2)
        cout << "DA\n";
    else
        cout << "NE\n";
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9