oj.uz

Submission #97510

# Submission time Handle Problem Language Result Execution time Memory
97510 2019-02-16T14:59:26 Z Milki Ispit (COCI19_ispit) C++14
9 / 90
 18 ms 992 KB 
#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
#define TRACE(x) cerr << #x << " = " << x << endl

typedef long long ll;
typedef pair<int, int> point;

const int MAXN = 505;
const int baza[8] = {1307, 991, 863, 877, 3083, 3089, 4091, 5471};
const int mod[8] = {1000000007, 1000000009, 1000000007, 1000000009, 1000000007, 1000000009, 1000000007, 1000000009};
const int brojBaza = 4;

int add(int x, int y, int id){
  x += y;
  if(x >= mod[id]) return x - mod[id];
  if(x < 0) return x + mod[id];
  return x;
}

int mul(ll x, ll y, int id){
  return x * y % mod[id];
}

int n, k;
char a[MAXN][MAXN];
int hesh[MAXN][brojBaza], pot[30][brojBaza];
unordered_map<int, int> M[brojBaza];

void finish(){
  cout << "DA";
  exit(0);
}

void check(){
  REP(i, n){
    bool ok = true;
    REP(j, brojBaza){
      if(M[j][hesh[i][j]] <= 1){
        ok = false;
        break;
      }
    }
    if(ok) finish();
  }
}

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);

  REP(i, brojBaza)
    pot[0][i] = 1;
  REP(i, brojBaza)
    FOR(j, 1, 30)
      pot[j][i] = mul(pot[j - 1][i], baza[i], i);

  cin >> n >> k;

  REP(i, n) REP(j, n) cin >> a[i][j];

  REP(i, n)
    REP(j, brojBaza)
      hesh[i][j] = a[i][0];

  REP(currBase, brojBaza)
    REP(i, n)
      FOR(j, 1, k)
        hesh[i][currBase] = add(hesh[i][currBase], pot[a[i][j] - 'a'][currBase], currBase);

  REP(currBase, brojBaza)
    REP(i, n)
      M[currBase][hesh[i][currBase]] ++;
  check();

  FOR(j, k, n){
    REP(currBase, brojBaza){
      M[currBase].clear();
      REP(i, n){
        hesh[i][currBase] = add(hesh[i][currBase], pot[a[i][j] - 'a'][currBase], currBase);
        hesh[i][currBase] = add( - pot[ a[i][j - k] - 'a' ][currBase] , hesh[i][currBase], currBase );
        M[currBase][ hesh[i][currBase] ] ++;
      }
    }
    check();
  }
  cout << "NE";
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Incorrect 3 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Incorrect 4 ms 512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 576 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Incorrect 5 ms 512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Incorrect 5 ms 504 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Incorrect 5 ms 640 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 896 KB Output is correct
2 Correct 12 ms 896 KB Output is correct
3 Incorrect 12 ms 896 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 992 KB Output is correct
2 Incorrect 10 ms 896 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 896 KB Output is correct
2 Correct 15 ms 868 KB Output is correct
3 Incorrect 18 ms 888 KB Output isn't correct
4 Halted 0 ms 0 KB -