Submission #799717

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
799717	2023-07-31 20:51:28	tch1cherin	Genetics (BOI18_genetics)	C++17	100 / 100	461 ms	91736 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
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("sse4.1,sse4.2,avx,avx2,bmi,bmi2,lzcnt,popcnt,fma")
#include <bits/stdc++.h>
using namespace std;
 
template <const int N>
struct Bitset {
  uint64_t bs[(N + 63) >> 6] = {};
 
  void set(int i) { bs[i >> 6] |= 1ull << (i & 63); }
};
 
template <const int N>
int operator^(Bitset<N>& A, Bitset<N>& B) {
  int ans = 0;
  constexpr int C = (N + 63) >> 6;
  for (int i = 0; i < C; i++) {
    ans += __builtin_popcountll(A.bs[i] ^ B.bs[i]); 
  }
  return ans;
}
 
const int MAX_N = 4105;
Bitset<MAX_N> bs[MAX_N][4];
string S[MAX_N];
bool good[MAX_N];
int dist[MAX_N][MAX_N], cnt[MAX_N][4];
int to[128];
 
using R = uniform_int_distribution<int>;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:42:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   42 |       cnt[j][to[S[i][j]]]++;
      |                        ^
genetics.cpp:43:23: warning: array subscript has type 'char' [-Wchar-subscripts]
   43 |       bs[i][to[S[i][j]]].set(j);
      |                       ^
genetics.cpp:44:29: warning: array subscript has type 'char' [-Wchar-subscripts]
   44 |       msk |= 1 << to[S[i][j]];
      |                             ^
genetics.cpp:52:35: warning: array subscript has type 'char' [-Wchar-subscripts]
   52 |       sum += N - cnt[j][to[S[i][j]]];
      |                                   ^

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