Submission #653102

#	Time	Username	Problem	Language	Result	Execution time	Memory
653102		_martynas	Genetics (BOI18_genetics)	C++11	46 / 100	2027 ms	259876 KiB

genetics

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;

const int MOD = 1e9+7;

#define F first
#define S second
#define PB push_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

void FASTIO() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }

const int MXN = 4105;

mt19937 rng(0);
int n, m, k;
string S[MXN];
int A[4][MXN][MXN];
ull P[MXN];
ull ACC[4][MXN];
int c_to_id[256];

bool prime(ull x) {
    for(ull y = 2; y*y <= x; y++) {
        if(x % y == 0) {
            return false;
        }
    }
    return x != 1;
}

int main() {
    FASTIO();
    c_to_id['A'] = 0;
    c_to_id['C'] = 1;
    c_to_id['G'] = 2;
    c_to_id['T'] = 3;


    cin >> n >> m >> k;
    for(int c = 0; c < 4; c++)
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            A[c][i][j] = -1;
        }
    }

    for(int i = 0; i < n; i++) {
        P[i] = rng();
        while(!prime(P[i])) P[i]++;
    }

    for(int i = 0; i < n; i++) {
        string s; cin >> s; S[i] = s;
        for(int j = 0; j < m; j++) {
            int v = c_to_id[s[j]];
            A[v][i][j] = 1;
        }
    }

//    for(int i = 0; i < n; i++) {
//        //cerr << S[i] << "\n";
//        bool ok = true;
//        for(int j = 0; j < n; j++) {
//            if(i == j) continue;
//            int cnt = 0;
//            for(int c = 0; c < 4; c++) {
//                for(int u = 0; u < m; u++) {
//                    cnt += A[c][i][u]*A[c][j][u];
//                }
//            }
//            //cerr << "<> " << S[j] << ": " << cnt << "\n";
//            if(cnt != 4*(m-k)) {
//                ok = false;
//                break;
//            }
//        }
//        if(ok) {
//            cout << i+1 << "\n";
//        }
//    }

    for(int c = 0; c < 4; c++) {
        for(int u = 0; u < m; u++) {
            for(int i = 0; i < n; i++) {
                ACC[c][u] += A[c][i][u]*P[i];
            }
        }
    }

    for(int i = 0; i < n; i++) {
        //cerr << S[i] << "\n";
        ull prime_sum = accumulate(P, P+n, 0ULL);
        prime_sum -= P[i];// negate current row
        ll cnt = 0;
        for(int c = 0; c < 4; c++) {
            for(int u = 0; u < m; u++) {
                // Ai * Aj, j != i
                // Ai * [A1, A2, A3, ... Ai-1, Ai+1, ..., An], j != i
                // each col separately
                // Aiu * (A1u + A2u + ... Anu) (same operations made)
                // cnt += A[c][i][u]*A[c][j][u]; // x (n-1)
                cnt += A[c][i][u]*(ACC[c][u]-A[c][i][u]*P[i]);
            }
        }
        ll expected = 4*(m-k)*prime_sum;
        if(cnt == expected) {
            cout << i+1 << "\n";
        }
    }

    return 0;
}

/*
is A:
 1 -1  1  1 -1
-1  1 -1  1 -1
--------------
-1 -1 -1  1 1
= (potentially) same - different

A: (potentially) same - different
C: (potentially) same - different
G: (potentially) same - different
T: (potentially) same - different

A: true same - true different + maybe same

? -> C -> ? -> ? -> -1 + 1 = 0
?    ?    G    ?

? -> C -> ? -> ? ->  1 + 3 = 4
?    C    ?    ?

=> A+C+G+T = 4 * same symbol amount

p1  p1  p1  p1
p2 -p2  p2 -p2
p3  p3 -p3 -p3
p4  p4  p4  p4
 1  -1  -1   1




4 3 1
ACC
CCA
ACA
AAA
ans: 3

4 4 3
CATT
CAAA
ATGA
TCTA
ans: 4

*/

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:66:33: warning: array subscript has type 'char' [-Wchar-subscripts]
   66 |             int v = c_to_id[s[j]];
      |                                 ^

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