Submission #1095371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095371		vjudge1	Genetics (BOI18_genetics)	C++17	100 / 100	573 ms	148908 KiB

genetics

#include <bits/stdc++.h>

#define ll long long
#define fr(i, d, c) for(ll i = d; i <= c; i++)
#define fl(i, d, c) for(ll i = d; i >= c; i--)
const int N = 4100 + 9;
using namespace std;

mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
#define rand(l, r) uniform_int_distribution<long long> (l, r) (mt)
    
ll n, m, k, sum, a[N][N], p[N], cnt[N][4];
vector<ll> cur;

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  srand(time(NULL));
  cin >> n >> m >> k;
  fr(i, 1, n) {
    fr(j, 1, m) {
      char x;
      cin>> x;
      if(x == 'A') a[i][j] = 0;
      if(x == 'C') a[i][j] = 1;
      if(x == 'G') a[i][j] = 2;
      if(x == 'T') a[i][j] = 3;
    }
    cur.push_back(i);
  }

  fr(i, 1, n) {
    p[i] = rand(1, 1e9);
    sum += p[i];
  }

  fr(i, 1, n) {
    fr(j, 1, m) {
      fr(t, 0, 3) {
        if(t == a[i][j]) continue;
        cnt[j][t] += p[i];
      }
    }
  }

  while(cur.size() > 1) {
    ll id = rand(1, n), nx = rand(1, 1e9);
    sum += nx - p[id];
    fr(j, 1, m) {
      fr(t, 0, 3) {
        if(t == a[id][j]) continue;
        cnt[j][t] += nx - p[id];
      }
    }
    p[id] = nx;

    for(ll t = 0; t < cur.size(); t++) {
      ll i = cur[t];
      ll val = 0;
      fr(j, 1, m) {
        val += cnt[j][a[i][j]];
      }
      if(val != (sum - p[i]) * k) {
        swap(cur[t], cur.back());
        cur.pop_back();
        t--;
      }
    }
  }
  cout<<cur.back();
}

Compilation message (stderr)

genetics.cpp: In function 'int32_t main()':
genetics.cpp:57:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(ll t = 0; t < cur.size(); t++) {
      |                   ~~^~~~~~~~~~~~

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