Submission #720902

#	Time	Username	Problem	Language	Result	Execution time	Memory
720902		spike1236	Genetics (BOI18_genetics)	C++14	100 / 100	742 ms	36248 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 pb push_back
#define mp make_pair
#define f first
#define s second
#define ll long long
#define ld long double
#define all(_v) _v.begin(), _v.end()
#define sz(_v) (int)_v.size()
#define pii pair <int, int>
#define pll pair <ll, ll>
#define veci vector <int>
#define vecll vector <ll>

// template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
// mt19937_64 rnd64(chrono::steady_clock::now().time_since_epoch().count());

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
const double PI = 3.141592653589793;
const double eps = 1e-9;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;

int n, m, K;
ll a[4110];
string s[4110];
ll sum[4];
ll dp[4110];

void solve() {
    cin >> n >> m >> K;
    ll sumhash = 0;
    for(int i = 1; i <= n; ++i) {
        cin >> s[i];
        a[i] = rnd();
        sumhash += a[i];
    }
    for(int j = 0; j < m; ++j) {
        memset(sum, 0, sizeof(sum));
        for(int i = 1; i <= n; ++i) {
            int x = 0;
            if(s[i][j] == 'A') x = 0;
            if(s[i][j] == 'C') x = 1;
            if(s[i][j] == 'G') x = 2;
            if(s[i][j] == 'T') x = 3;
            sum[x] += a[i];
        }
        for(int i = 1; i <= n; ++i) {
            int x = 0;
            if(s[i][j] == 'A') x = 0;
            if(s[i][j] == 'C') x = 1;
            if(s[i][j] == 'G') x = 2;
            if(s[i][j] == 'T') x = 3;
            for(int k = 0; k < 4; ++k) if(x != k) dp[i] += sum[k];
        }
    }
    for(int i = 1; i <= n; ++i) {
        if((sumhash - a[i]) * K == dp[i]) {
            cout << i;
            return;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int CNT_TESTS = 1;
    // cin >> CNT_TESTS;
    for(int NUMCASE = 1; NUMCASE <= CNT_TESTS; ++NUMCASE) {
        solve();
        if(NUMCASE != CNT_TESTS) cout << '\n';
    }
    return 0;
}

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