Submission #876490

#	Time	Username	Problem	Language	Result	Execution time	Memory
876490		hazzle	Genetics (BOI18_genetics)	C++17	100 / 100	510 ms	36468 KiB

genetics

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx,avx2,fma")

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define all(m) (m).begin(), (m).end()
#define rall(m) (m).rbegin(), (m).rend()
#define vec vector
#define sz(a) (int) (a).size()
#define mpp make_pair
#define mtt make_tuple

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;
typedef tuple <int, int, int> tui;

template <typename T>
using prq = priority_queue <T>;

template <typename T>
using pgq = priority_queue <T, vec <T>, greater <T>>;

template <typename T> bool umin(T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> bool umax(T &a, T b) { return a < b ? a = b, 1 : 0; }

const uint32_t mod = 1e9 + 7;
//const uint32_t mod = 998244353;

struct mint{
      inline uint32_t nrm(int a){
            if (a >= mod) a -= mod;
            return a;
      }

      uint32_t x;

      mint(): x(0) {}

      mint(ll a) {
            a %= mod;
            if (a < 0) a += mod;
            x = a;
      }

      mint& operator+=(const mint &b){
            x = nrm(x + b.x);
            return *this;
      }
      mint& operator-=(const mint &b){
            x = nrm(mod + x - b.x);
            return *this;
      }
      mint& operator*=(const mint &b){
            x = x * ll(b.x) % mod;
            return *this;
      }

      mint bpw(ll b) const {
            mint r = 1, a = *this;
            for (; b; b >>= 1, a *= a){
                  if (b & 1) r *= a;
            }
            return r;
      }
      mint inv() const {
            uint32_t t = x, res = 1;
            while(t != 1){
                  uint32_t d = mod / t;
                  res = res * ll(mod - d) % mod;
                  t = mod - t * d;
            }
            return res;
      }

      mint& operator /=(const mint &b){
            return *this *= b.inv();
      }

      mint operator+(const mint &b) const {
            return mint(*this) += b;
      }
      mint operator-(const mint &b) const {
            return mint(*this) -= b;
      }
      mint operator*(const mint &b) const {
            return mint(*this) *= b;
      }
      mint operator/(const mint &b) const {
            return mint(*this) /= b;
      }

      bool operator==(const mint &b) const {
            return x == b.x;
      }
      bool operator!=(const mint &b) const {
            return x != b.x;
      }
      bool operator<(const mint &b) const {
            return x < b.x;
      }
      bool operator>(const mint &b) const {
            return x > b.x;
      }

      friend istream& operator>>(istream &in, mint &a) { in >> a.x; return in; }
      friend ostream& operator<<(ostream &out, const mint &a) { out << a.x; return out; }
};

mt19937 rng((uint64_t) new char);
string alph = "ACGT";

inline int solve(){
      int n, m, k;
      cin >> n >> m >> k;
      vec <string> s(n);
      for (auto &i: s) cin >> i;
      vec <mint> val(n);
      mint sum = 0;
      for (int i = 0; i < n; ++i){
            sum += (val[i] = rng());
      }
      auto con = [&](char c){
            return find(all(alph), c) - alph.begin();
      };
      vec <vec <mint>> vals(m, vec <mint> (4));
      for (int i = 0; i < n; ++i){
            for (int j = 0; j < m; ++j){
                  vals[j][con(s[i][j])] += val[i];
            }
      }
      for (int i = 0; i < n; ++i){
            mint hah = 0;
            for (int j = 0; j < m; ++j){
                  for (char c: alph){
                        if (c != s[i][j]){
                              hah += vals[j][con(c)];
                        }
                  }
            }
            if (hah == (sum - val[i]) * k){
                  cout << i + 1 << "\n";
                  return 0;
            }
      }
      return 0;
}

inline void precalc(){}

signed main(){
      ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
      int tst = 1; //cin >> tst;
      precalc();
      while(tst--) solve();
      return 0;
}

Compilation message (stderr)

genetics.cpp: In member function 'uint32_t mint::nrm(int)':
genetics.cpp:40:19: warning: comparison of integer expressions of different signedness: 'int' and 'const uint32_t' {aka 'const unsigned int'} [-Wsign-compare]
   40 |             if (a >= mod) a -= mod;
      |                 ~~^~~~~~

• Subtask 1: 27 / 27
• Subtask 2: 19 / 19
• Subtask 3: 28 / 28
• Subtask 4: 26 / 26