Submission #834498

#	Time	Username	Problem	Language	Result	Execution time	Memory
834498		Victor	Genetics (BOI18_genetics)	C++17	100 / 100	175 ms	36356 KiB

genetics

// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    ll w[4101], sumw = 0, col_sum[4101][4];
    memset(col_sum, 0, sizeof(col_sum));
    string dna[4101];
    int n, m, k;

    cin >> n >> m >> k;
    rep(i, 0, n) {
        cin >> dna[i];
        w[i] = ll(rand()) * rand() % ll(1e14) + 1;
        sumw += w[i];

        int col = 0;
        trav(let, dna[i]) {
            let = let == 'A' ? 0 : let == 'C' ? 1
                               : let == 'G'   ? 2
                                              : 3;
            col_sum[col][let] += w[i];
            ++col;
        }
    }

    int ans;
    rep(i, 0, n) {
        ll sum = 0;
        rep(j, 0, m) rep(l, 0, 4) sum += col_sum[j][l] * (l != dna[i][j]);
        if(sum==k*(sumw-w[i])){
            ans=i+1;
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:53:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   53 |             col_sum[col][let] += w[i];
      |                          ^~~
genetics.cpp:67:13: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   67 |     cout << ans << endl;
      |             ^~~

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