Submission #871641

#	Time	Username	Problem	Language	Result	Execution time	Memory
871641		LittleFlowers__	Genetics (BOI18_genetics)	C++17	100 / 100	368 ms	46372 KiB

genetics

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>

using namespace std;

string to_string(string s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
mt19937 rng(101202);
#else
#define debug(...) 42
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#endif

#define in ({int x = 0; int c = getchar(), n = 0; for(; !isdigit(c); c = getchar()) n = (c == '-'); for(; isdigit(c); c = getchar()) x = x * 10 + c - '0'; n ? -x : x;})

int rnd(int l,int r) {
  if (l > r) { cerr << l << " " << r << "\n"; }
  return l + rng() % (r - l + 1);
}

const int N = 4210;

int n, m, k;
int cnt[N * 4][26];
string t[N];
bitset<N * 4> mask[N];

int32_t main() {
  if (fopen("input.txt", "r")) {
    freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
  }

  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m >> k; k = m - k;
  for (int i = 1; i <= n; ++i) {
    cin >> t[i];
    const string &s = t[i];
    for (int j = 0; j < m; ++j) {
      int p = s[j] == 'A' ? 0 : s[j] == 'C' ? 1 : s[j] == 'G' ? 2 : 3;
      mask[i][p * m + j].flip();

      cnt[j][s[j] - 'A'] += 1;
    }
  }

  vector<int> candidates;
  for (int i = 1; i <= n; ++i) {
    int sumvalid = 0;
    for (int j = 0; j < m; ++j) sumvalid += cnt[j][t[i][j] - 'A'];
    if (sumvalid == k * (n - 1) + m) candidates.push_back(i);
  }

  vector<int> p(n);
  iota(p.begin(), p.end(), 1);
  shuffle(p.begin(), p.end(), rng);

  for (const int &i : candidates) {
    bool valid = true;
    for (const int &j : p) {
      if (i == j) continue;
      int c = (mask[i] & mask[j]).count();
      if (c != k) { 
        valid = false;
        break;
      }
    }

    if (valid) return cout << i << '\n', 0;
  }
}

Compilation message (stderr)

genetics.cpp: In function 'int32_t main()':
genetics.cpp:72:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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