oj.uz

답안 #853533

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
853533 2023-09-24T14:21:10 Z HoriaHaivas Ispit (COCI19_ispit) C++14
90 / 90
 44 ms 3416 KB 
/*
    "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.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 4 ms 2652 KB Output is correct
4 Correct 3 ms 2652 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2652 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 3 ms 2652 KB Output is correct
4 Correct 3 ms 2652 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 3 ms 2652 KB Output is correct
4 Correct 3 ms 2648 KB Output is correct

Subtask #7
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 3 ms 2652 KB Output is correct
4 Correct 4 ms 2652 KB Output is correct

Subtask #8
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 2652 KB Output is correct
2 Correct 9 ms 3072 KB Output is correct
3 Correct 15 ms 3416 KB Output is correct
4 Correct 13 ms 3160 KB Output is correct

Subtask #9
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 2652 KB Output is correct
2 Correct 10 ms 2908 KB Output is correct
3 Correct 28 ms 3224 KB Output is correct
4 Correct 44 ms 3188 KB Output is correct

Subtask #10
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 2652 KB Output is correct
2 Correct 9 ms 2896 KB Output is correct
3 Correct 28 ms 3164 KB Output is correct
4 Correct 17 ms 3164 KB Output is correct