//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const ll inf = 1e18;
const int M = 4100;
random_device rd;
struct bits{
int n, k; // size and block_count
unsigned long long *b;
int cnt; // count of set bits
inline void init(int _n){
n = _n;
k = (n + 63) / 64;
cnt = 0;
b = (unsigned long long *) calloc(k, sizeof(unsigned long long));
}
bits(){};
bits(int _n){
init(_n);
}
bits(const bits& from) : n(from.n), k(from.k), cnt(from.cnt){
b = (unsigned long long *) calloc(k, sizeof(unsigned long long));
memcpy(b, from.b, sizeof(b));
};
void set(int i){
assert(0 <= i && i < n);
if (!((b[i / 64] >> (i % 64)) & 1)){
cnt++;
b[i / 64] |= (1ull << (i % 64));
}
}
void reset(int i){
assert(0 <= i && i < n);
if ((b[i / 64] >> (i % 64)) & 1){
cnt--;
b[i / 64] &= ULLONG_MAX ^ (1ull << (i % 64));
}
}
void flip(int i){
assert(0 <= i && i < n);
if ((b[i / 64] >> (i % 64)) & 1){
reset(i);
} else {
set(i);
}
}
void set(){
cnt = n;
for (int i = 0; i + 1 < k; i++) b[i] = ULLONG_MAX;
b[k - 1] = (1ull << (n % 64)) - 1;
}
void reset(){
cnt = 0;
for (int i = 0; i < k; i++) b[i] = 0;
}
void flip(){
cnt = n - cnt;
for (int i = 0; i + 1 < k; i++) b[i] ^= ULLONG_MAX;
b[k - 1] ^= (1ull << (n % 64)) - 1;
}
bool test(int i) const{
assert(0 <= i && i < n);
return (b[i / 64] >> (i % 64)) & 1;
}
int count() const{
return cnt;
}
bool any_of() const{
return cnt > 0;
}
bool none_of() const{
return cnt == 0;
}
bool all_of() const{
return cnt == n;
}
int find_first(){
if (cnt == 0) return n;
int i = 0;
while (i < k && b[i] == 0) i++;
return i * 64 + __builtin_ctzll(b[i]);
}
int find_next(int i){ // first set bit >= i
int j = i / 64;
unsigned long long val = b[j];
val &= ULLONG_MAX ^ ((1ull << (i % 64)) - 1);
if (val != 0) return j * 64 + __builtin_ctzll(val);
j++;
while (j < k && b[j] == 0) j++;
if (j == k) return n;
return j * 64 + __builtin_ctzll(b[j]);
}
bits operator|= (const bits &other){
assert(n == other.n);
cnt = 0;
for (int i = 0; i < k; i++){
this->b[i] |= other.b[i];
cnt += __builtin_popcountll(this->b[i]);
}
return *this;
}
bits operator| (const bits &other){
bits res = *this;
res |= other;
return res;
}
bits operator&= (const bits &other){
assert(n == other.n);
cnt = 0;
for (int i = 0; i < k; i++){
this->b[i] &= other.b[i];
cnt += __builtin_popcountll(this->b[i]);
}
return *this;
}
bits operator& (const bits &other){
bits res = *this;
res &= other;
return res;
}
bits operator^= (const bits &other){
assert(n == other.n);
cnt = 0;
for (int i = 0; i < k; i++){
this->b[i] ^= other.b[i];
cnt += __builtin_popcountll(this->b[i]);
}
return *this;
}
bits operator^ (const bits &other){
bits res = *this;
res ^= other;
return res;
}
bits operator>>= (const int t){
if (t >= n){
reset();
} else {
for (int i = t; i < n; i++) {
if (test(i)) {
set(i - t);
} else {
reset(i - t);
}
}
for (int i = n - t; i < n; i++) {
reset(i);
}
}
return *this;
}
bits operator>> (const int t){
bits res = *this;
res >>= t;
return res;
}
bits operator<<= (const int t){
if (t >= n){
reset();
} else {
for (int i = n - t - 1; i >= 0; i--) {
if (test(i)) {
set(i + t);
} else {
reset(i + t);
}
}
for (int i = 0; i < t; i++) {
reset(i);
}
}
return *this;
}
bits operator<< (const int t){
bits res = *this;
res <<= t;
return res;
}
};
int main() {
srand(time(0));
cin.tie(0)->sync_with_stdio(false);
#ifdef sunnatov
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int n, m, k;
cin >> n >> m >> k;
vector<string> a(n);
for (string &s: a) cin >> s;
vector<bits> bs(n);
for (int i = 0; i < n; i++) bs[i].init(4 * m);
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
if (a[i][j] == 'A') bs[i].set(4 * j);
if (a[i][j] == 'C') bs[i].set(4 * j + 1);
if (a[i][j] == 'G') bs[i].set(4 * j + 2);
if (a[i][j] == 'T') bs[i].set(4 * j + 3);
}
vector ok(n, vector(n, -1));
vector<int> pos(n);
iota(pos.begin(), pos.end(), 0);
shuffle(pos.begin(), pos.end(), rd);
for (int i = 0; i < min(10, n); i++) {
for (int j = 0; j < n; j++) {
if (pos[i] == j) continue;
if ((bs[pos[i]] ^ bs[j]).count() != 2 * k) {
ok[pos[i]][j] = ok[j][pos[i]] = 0;
}
}
}
for (int i = 0; i < n; i++) {
if (count(ok[i].begin(), ok[i].end(), 0)) continue;
for (int j = 0; j < n; j++) {
if (i == j or ok[i][j] == 1) continue;
if ((bs[i] ^ bs[j]).count() != 2 * k) {
ok[i][j] = ok[j][i] = 0;
break;
} else {
ok[i][j] = ok[j][i] = 1;
}
}
if (!count(ok[i].begin(), ok[i].end(), 0)) {
cout << i + 1;
return 0;
}
}
}
Compilation message
alternating.cpp: In copy constructor 'bits::bits(const bits&)':
alternating.cpp:31:27: warning: argument to 'sizeof' in 'void* memcpy(void*, const void*, size_t)' call is the same expression as the destination; did you mean to dereference it? [-Wsizeof-pointer-memaccess]
31 | memcpy(b, from.b, sizeof(b));
| ^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Unexpected end of file - token expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Unexpected end of file - token expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Unexpected end of file - token expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
399 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Unexpected end of file - token expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
