Submission #473715

#	Time	Username	Problem	Language	Result	Execution time	Memory
473715		elgamalsalman	Genetics (BOI18_genetics)	C++14	27 / 100	2091 ms	7200 KiB

genetics

#include <bits/stdc++.h>

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
//
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

typedef long long ll;

int n, m, k, score[4150], validCount;
string codes[4150], originalCodes[4150];
bitset<4150> isValid;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  //Tree<int> oset;

  cin >> n >> m >> k;
  for (int i = 0; i < n; i++) {
    cin >> codes[i];
    originalCodes[i] = codes[i];
    //oset.insert(i);
  }

  isValid.set();

  srand(1932);
  random_shuffle(codes, codes + n);

  for (int i = 0; i < n; i++) { 
    if (!isValid[i]) continue;
    for (int j = 0; j < n; j++) {
      if (i == j) continue;

      int diffCount = 0;
      for (int c = 0; c < m; c++) if (codes[i][c] != codes[j][c]) diffCount++;
      if (diffCount != k) {
	isValid[i] = isValid[j] = 0;
	break;
      }
    }

    if (isValid[i]) return cout << distance(originalCodes, find(originalCodes, originalCodes + n, codes[i])) + 1 << '\n', 0;
  }
  
  //srand(2004);
  //while (oset.size() > 1) {
  //  int i = rand() % n, j = rand() % n;
  //  if (i == j) continue;
  //  i = *oset.find_by_order(i);
  //  j = *oset.find_by_order(j);

  //  int diffCount = 0;
  //  for (int c = 0; c < m; c++) if (codes[i][c] != codes[j][c]) diffCount++;
  //  if (diffCount != k) {
  //    if (n % 2) { oset.erase(i); n--; }
  //    oset.erase(j);
  //    n--;
  //  }
  //}

  //for (int i = 0; i < n; i++) cerr << "// score[" << i << "] : " << score[i] << '\n';

  //cout << *oset.begin() + 1 << '\n';
}

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