Submission #436528

#	Time	Username	Problem	Language	Result	Execution time	Memory
436528		codebuster_10	Genetics (BOI18_genetics)	C++17	100 / 100	1494 ms	291740 KiB

genetics

#include <bits/stdc++.h>
using namespace std;

#define int int64_t //be careful about this 
#define endl "\n"
#define f(i,a,b) for(int i=int(a);i<int(b);++i)

#define pr pair
#define ar array
#define fr first
#define sc second
#define vt vector
#define pb push_back
#define eb emplace_back
#define LB lower_bound  
#define UB upper_bound
#define PQ priority_queue

#define SZ(x) ((int)(x).size())
#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define mem(a,b) memset(a, b, sizeof(a))

template<class A> void rd(vt<A>& v);
template<class T> void rd(T& x){ cin >> x; }
template<class H, class... T> void rd(H& h, T&... t) { rd(h) ; rd(t...) ;}
template<class A> void rd(vt<A>& x) { for(auto& a : x) rd(a) ;}

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

template<typename T>
void __p(T a) {
  cout<<a; 
}
template<typename T, typename F>
void __p(pair<T, F> a) {
  cout<<"{";
  __p(a.first);
  cout<<",";
  __p(a.second);
  cout<<"}\n"; 
}
template<typename T>
void __p(std::vector<T> a) {
  cout<<"{";
  for(auto it=a.begin(); it<a.end(); it++)
    __p(*it),cout<<",}\n"[it+1==a.end()]; 
}
template<typename T, typename ...Arg>
void __p(T a1, Arg ...a) {
  __p(a1);
  __p(a...);
}
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
  cout<<name<<" : ";
  __p(arg1);
  cout<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
  int bracket=0,i=0;
  for(;; i++)
    if(names[i]==','&&bracket==0)
      break;
    else if(names[i]=='(')
      bracket++;
    else if(names[i]==')')
      bracket--;
  const char *comma=names+i;
  cout.write(names,comma-names)<<" : ";
  __p(arg1);
  cout<<" | ";
  __f(comma+1,args...);
}

void setIO(string s = "") {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
  cin.exceptions(cin.failbit); 
	cout.precision(15);	cout << fixed;
  if(SZ(s)){
  	freopen((s+".in").c_str(),"r",stdin);
  	freopen((s+".out").c_str(),"w",stdout);
  }
}






















/**
 * Description :- modular arithmetic operations
 * Source :- https://codeforces.com/contest/1342/submission/78409946
 * Verification:- https://open.kattis.com/problems/modulararithmetic
 */

template<const int &MOD>
struct _m_int {
  int val;

  _m_int(int64_t v = 0) {
    if(v < 0) v = v % MOD + MOD;
    if(v >= MOD) v %= MOD;
    val = v;
  }

  static int inv_mod(int a, int m = MOD) {
    // https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Example
    int g = m, r = a, x = 0, y = 1;

    while(r != 0) {
      int q = g / r;
      g %= r; swap(g, r);
      x -= q * y; swap(x, y);
    }
    return x < 0 ? x + m : x;
  }
  // wont work if we use #define int int64_t
  // explicit operator int() const { return val; }
  explicit operator int64_t() const { return val; }

  _m_int& operator+=(const _m_int &other) {
    val -= MOD - other.val;
    if(val < 0) val += MOD;
    return *this;
  }

  _m_int& operator-=(const _m_int &other) {
    val -= other.val;
    if(val < 0) val += MOD;
    return *this;
  }

  static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
#if !defined(_WIN32) || defined(_WIN64)
    return x % m;
#endif
    // Optimized mod for Codeforces 32-bit machines.
    // x must be less than 2^32 * m for this to work, so that x / m fits in a 32-bit unsigned int.
    unsigned x_high = x >> 32, x_low = (unsigned) x;
    unsigned quot, rem;
    asm("divl %4\n"
      : "=a" (quot), "=d" (rem)
      : "d" (x_high), "a" (x_low), "r" (m));
    return rem;
  }

  _m_int& operator*=(const _m_int &other) {
    val = fast_mod((uint64_t) val * other.val);
    return *this;
  }

  _m_int& operator/=(const _m_int &other) {
    return *this *= other.inv();
  }

  friend _m_int operator+(const _m_int &a, const _m_int &b) { return _m_int(a) += b; }
  friend _m_int operator-(const _m_int &a, const _m_int &b) { return _m_int(a) -= b; }
  friend _m_int operator*(const _m_int &a, const _m_int &b) { return _m_int(a) *= b; }
  friend _m_int operator/(const _m_int &a, const _m_int &b) { return _m_int(a) /= b; }

  _m_int& operator++() {
    val = val == MOD - 1 ? 0 : val + 1;
    return *this;
  }

  _m_int& operator--() {
    val = val == 0 ? MOD - 1 : val - 1;
    return *this;
  }

  // wont work if we use #define int int64_t
  // _m_int operator++(int) { _m_int before = *this; ++*this; return before; }
  // _m_int operator--(int) { _m_int before = *this; --*this; return before; }

  _m_int operator-() const {
    return val == 0 ? 0 : MOD - val;
  }

  bool operator==(const _m_int &other) const { return val == other.val; }
  bool operator!=(const _m_int &other) const { return val != other.val; }

  _m_int inv() const {
    return inv_mod(val);
  }

  _m_int pow(int64_t p) const {
    if(p < 0)	return inv().pow(-p);
    _m_int a = *this, result = 1;
    while(p > 0) {
      if(p & 1)	result *= a;
      a *= a;
      p >>= 1;
    }
    return result;
  }

  friend ostream& operator<<(ostream &os, const _m_int &m) {
    return os << m.val;
  }
};

extern const int MOD = int(1e9) + 7;
using mint = _m_int<MOD>;

#define rand __rand

auto random_address = [] { char *p = new char; delete p; return uint64_t(p); };
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count() * (random_address() | 1));
int rand(int L = 0,int R = int(1e9)){
  return uniform_int_distribution<int>(L,R)(rng) ;
}



const int HASH_COUNT = 2;
const int BASE[] = {rand(0.1 * MOD, 0.9 * MOD), rand(0.1 * MOD, 0.9 * MOD)};

const string LETTERS = "ATGC";








































signed main(){
  setIO();
  int N,M,K;
  rd(N,M,K);
  K = M-K; // number of same chars.
	
	
	vt<mint> pow[2];
	
	for(int i = 0; i < HASH_COUNT; ++i){
		for(int j = 0; j < N; ++j){
			pow[i].pb(mint(BASE[i]).pow(j));
		}
	}
	  
  vt<string> s(N);
  rd(s);
  
  vt<vt<mint>> a[HASH_COUNT];
  
  for(int i = 0; i < HASH_COUNT; ++i){
  	a[i] = vt<vt<mint>>(M,vt<mint>(N));
  }
  
  vt<mint> total[HASH_COUNT][SZ(LETTERS)];
  
  for(int j = 0; j < HASH_COUNT; ++j){
  	for(int  i = 0; i < SZ(LETTERS); ++i){
  		total[j][i] = vt<mint> (M);
  	}
  }
  
  // value if a[i][j] is activated.
  for(int i = 0; i < M; ++i){
  	for(int j = 0; j < N; ++j){
  		for(int k = 0; k < HASH_COUNT; ++k){
  			a[k][i][j] = pow[k][j];
  			for(int u = 0; u <  SZ(LETTERS); ++u) if(LETTERS[u] == s[j][i]){
  				total[k][u][i] += a[k][i][j];
  			}
  		}
  	}
  }
  
  mint NEED[HASH_COUNT];
  for(int i = 0; i < N; ++i){
  	for(int j = 0; j < HASH_COUNT; ++j){
  		NEED[j] += K * pow[j][i];
  	}
  }
  
  for(int i = 0; i < N; ++i){
  	mint need[HASH_COUNT];
  	for(int j = 0; j < HASH_COUNT; ++j){
  		need[j] = NEED[j] + (M - K) * pow[j][i];
  	}
  	
  	for(int j = 0; j < M; ++j){
  		for(int k = 0; k < HASH_COUNT; ++k){
  			for(int u = 0; u <  SZ(LETTERS); ++u) if(LETTERS[u] == s[i][j]){
  				need[k] -= total[k][u][j];
  			}
  		}
  	}
  	
  	bool ok = true;
  	for(int j = 0; j < HASH_COUNT; ++j){
  		ok &= need[j] == mint(0);
  	}
  	
  	if(ok){
  		cout << i + 1; exit(0);
  	}
  }
  
  assert(false);
}

Compilation message (stderr)

genetics.cpp: In function 'void setIO(std::string)':
genetics.cpp:83:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |    freopen((s+".in").c_str(),"r",stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
genetics.cpp:84:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |    freopen((s+".out").c_str(),"w",stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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