Submission #866395

#	Time	Username	Problem	Language	Result	Execution time	Memory
866395		The_Samurai	Alternating Current (BOI18_alternating)	C++17	0 / 100	399 ms	1048576 KiB

alternating

//#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 (stderr)

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));
      |                           ^~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 22
• Subtask 4: 0 / 19
• Subtask 5: 0 / 26