Submission #456405

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
456405	2021-08-06 16:34:06	nonsensenonsense1	Genetics (BOI18_genetics)	C++17	100 / 100	1490 ms	43040 KiB

genetics

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cstdio>
#include <algorithm>
#include <random>
#include <chrono>
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
const int N = 4100;
const int K = 20;
unsigned long long a[N][(N - 1 >> 6) + 1][4];
int n, m, x, ord[N], mask[N], p[N], subset_size[K], in[K][N][4];
bool u[N][N], bad[N], inc[K][N];
int count_xor(unsigned long long (*a)[4], unsigned long long (*b)[4]) 
{
  int s = 0;
  for (int i = 0; i << 6 < m && s >> 1 <= x; ++i) {
    s += __builtin_popcountll(a[i][0] ^ b[i][0]);
    s += __builtin_popcountll(a[i][1] ^ b[i][1]);
    s += __builtin_popcountll(a[i][2] ^ b[i][2]);
    s += __builtin_popcountll(a[i][3] ^ b[i][3]);
  }
  return s >> 1;
}
void test(int p, int q) 
{
  if (u[p][q]) return;
  u[p][q] = u[q][p] = true;
  if (count_xor(a[p], a[q]) != x) bad[p] = bad[q] = 1;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

genetics.cpp:10:28: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   10 | unsigned long long a[N][(N - 1 >> 6) + 1][4];
      |                          ~~^~~
genetics.cpp: In function 'int main()':
genetics.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |  scanf("%d%d%d", &n, &m, &x);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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