Submission #97510

#	Time	Username	Problem	Language	Result	Execution time	Memory
97510		Milki	Ispit (COCI19_ispit)	C++14	9 / 90	18 ms	992 KiB

Main

#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
• Subtask 2: 9 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9