Submission #566340

#	Time	Username	Problem	Language	Result	Execution time	Memory
566340		tranxuanbach	Genetics (BOI18_genetics)	C++17	100 / 100	300 ms	66520 KiB

genetics

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

using ull = unsigned long long;

mt19937_64 rando(chrono::steady_clock::now().time_since_epoch().count());

const int N = 4100 + 5;

int valchar[256];

int n, m, k;
int a[N][N];

ull hshrow[N];

ull hshcolsame[N][5];

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("KEK.inp", "r", stdin);
    // freopen("KEK.out", "w", stdout);
    valchar['A'] = 1;
    valchar['C'] = 2;
    valchar['G'] = 3;
    valchar['T'] = 4;
    
    cin >> n >> m >> k;
    ForE(i, 1, n){
        string s; cin >> s; s = ' ' + s;
        ForE(j, 1, m){
            a[i][j] = valchar[s[j]];
        }
    }
    
    ForE(i, 1, n){
        hshrow[i] = rando();
    }
    ForE(i, 1, n){
        ForE(j, 1, m){
            hshcolsame[j][a[i][j]] += hshrow[i];
        }
    }
    
    ForE(i, 1, n){
        ull hsh1 = 0, hsh2 = 0;
        ForE(ti, 1, n){
            if (ti == i){
                continue;
            }
            hsh2 += hshrow[ti] * k;
        }
        ForE(j, 1, m){
            ForE(c, 1, 4){
                if (c != a[i][j]){
                    hsh1 += hshcolsame[j][c];
                }
            }
        }
        if (hsh1 == hsh2){
            cout << i << endl;
            return 0;
        }
    }
}

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:53:35: warning: array subscript has type 'char' [-Wchar-subscripts]
   53 |             a[i][j] = valchar[s[j]];
      |                                   ^

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