oj.uz

Submission #96660

# Submission time Handle Problem Language Result Execution time Memory
96660 2019-02-10T16:27:43 Z noneTP Ispit (COCI19_ispit) C++14
90 / 90
 472 ms 640 KB 
#include <bits/stdc++.h>
using namespace std;
typedef tuple<int, int, int> tp;
typedef long long LL;
typedef long double LD;
typedef pair<int, int> pii;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
typedef pair<LL, LL> pll;
typedef pair<pii, int> piipi;
typedef pair<int, pii> pipii;
typedef pair<pii, pii> piipii;
typedef pair<LL, pii> plpii;
typedef pair<LD, LD> pdd;
typedef pair<LD, int> pdi;
typedef pair<LD, LL> pdl;
typedef pair<int, LD> pid;
typedef pair<LL, LD> pld;
const int mod = 1e9 + 7;
const int hf = 999983;
const int N = 1e6;

char s[555][555];
int fi[555], se[555];
int hv[555];
int cnt[555];
int main(){
    hv[0] = 1;
    for(int i=1;i<=555-1;i++) hv[i] = (hv[i-1]*1ll*hf)%mod;
    int n, k;
    scanf("%d%d", &n, &k);
    bool ok = 0;
    for(int i=1;i<=n;i++) scanf("%s", s[i]+1);
    for(int l=1;l<=n-k+1;l++){
        int r = l+k-1;
        memset(fi, 0, sizeof(fi));
        memset(se, 0, sizeof(se));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=l-1;j++) fi[i] = (fi[i] + hv[j]*1ll*s[i][j])%mod;
            for(int j=r+1;j<=n;j++) fi[i] = (fi[i] + hv[j]*1ll*s[i][j])%mod;

            memset(cnt, 0, sizeof(cnt));
            for(int j=l;j<=r;j++) cnt[s[i][j]-'a']++;
            for(int j=0;j<26;j++) se[i] = (se[i] + hv[j]*1ll*cnt[j])%mod;

        }
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                if(fi[i] == fi[j] && se[i] == se[j]) ok = 1;
            }
        }
    }
    if(ok) printf("DA\n");
    else printf("NE\n");
}

Compilation message

ispit.cpp: In function 'int main()':
ispit.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~
ispit.cpp:33:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++) scanf("%s", s[i]+1);
                           ~~~~~^~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 23 ms 376 KB Output is correct
4 Correct 23 ms 504 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 14 ms 504 KB Output is correct
4 Correct 14 ms 504 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 8 ms 504 KB Output is correct
4 Correct 8 ms 376 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 18 ms 376 KB Output is correct
4 Correct 22 ms 376 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 632 KB Output is correct
2 Correct 11 ms 632 KB Output is correct
3 Correct 28 ms 640 KB Output is correct
4 Correct 30 ms 632 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 632 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 472 ms 640 KB Output is correct
4 Correct 471 ms 632 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 632 KB Output is correct
2 Correct 13 ms 632 KB Output is correct
3 Correct 161 ms 636 KB Output is correct
4 Correct 164 ms 632 KB Output is correct