Submission #653096

#	Time	Username	Problem	Language	Result	Execution time	Memory
653096		_martynas	Genetics (BOI18_genetics)	C++11	27 / 100	2070 ms	70864 KiB

genetics

#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2")
#include <bits/stdc++.h>

using namespace std;

using ll = 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;

int n, m, k;
string S[MXN];
int A[4][MXN][MXN];
int c_to_id[256];

void solve() {

}

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++) {
        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";
        }
    }



    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 -> ? -> ? -> -2 + 2 = 0
?    ?    G    ?

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

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

ATGA
TCTA
A: 3 - 1 =  2
C: 3 - 1 =  2
G: 3 - 1 =  2
T: 1 - 3 = -2

CAAA
ATGA
A: 1 - 3 = -2
C: 3 - 1 =  2
G: 3 - 1 =  2
T: 3 - 1 =  2


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:52:33: warning: array subscript has type 'char' [-Wchar-subscripts]
   52 |             int v = c_to_id[s[j]];
      |                                 ^

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