oj.uz

Submission #952636

# Submission time Handle Problem Language Result Execution time Memory
952636 2024-03-24T12:19:55 Z Ellinor Genetics (BOI18_genetics) C++14
0 / 100
 141 ms 6388 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
#pragma GCC optimize("unroll-loops")
#pragma GCC target("bmi,bmi2,lzcnt,popcnt") // bit manipulation
#pragma GCC target("movbe")                 // byte swap
#pragma GCC target("aes,pclmul,rdrnd")      // encryption
#pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2")

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define rep(i, a, b) for (int i = (a); i < int(b); i++)     // in , ex
#define rrep(i, a, b) for (int i = (a)-1; i >= int(b); i--) // ex, in
#define pb push_back
#define all(x) x.begin(), x.end()

inline void fast()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const ll INF = 100000000000000000; // 1e17
const ll MOD = 1e9 + 7;

//

random_device rd;
mt19937 rng(rd());
template <typename T>
inline T randint(T lo, T hi) { return uniform_int_distribution<T>(lo, hi)(rng); }

#define int ll
#define float double

//

int N, M, K;
vector<string> ns;

vector<bool> na;

vector<array<int, 4>> sum; // A, C, G, T

int32_t main()
{
    fast();

    cin >> N >> M >> K;

    ns.assign(N, "");
    rep(i, 0, N) cin >> ns[i];

    //

    sum.assign(N, {0, 0, 0, 0});

    rep(i, 0, N)
    {
        rep(j, 0, M)
        {
            if (ns[i][j] == 'A')
                sum[j][0]++;
            else if (ns[i][j] == 'C')
                sum[j][1]++;
            else if (ns[i][j] == 'G')
                sum[j][2]++;
            else
                sum[j][3]++;
        }
    }

    na.assign(N, true);

    rep(i, 0, N)
    {
        ll cnt = 0;

        rep(j, 0, M)
        {
            if (ns[i][j] == 'A')
                cnt += (N - sum[j][0]);
            else if (ns[i][j] == 'C')
                cnt += (N - sum[j][1]);
            else if (ns[i][j] == 'G')
                cnt += (N - sum[j][2]);
            else
                cnt += (N - sum[j][3]);
        }

        if (cnt % (N - 1) == 0)
        {
            cnt /= (N - 1);

            if (cnt != K)
                na[i] = false;
        }
        else
            na[i] = false;
    }

    //

    rep(i, 0, N)
    {
        if (!na[i])
            continue;

        rep(j, 0, N)
        {
            if (j == i)
                continue;

            int cnt = 0;

            rep(k, 0, M)
            {
                if (ns[i][k] != ns[j][k])
                    cnt++;
            }

            if (cnt != K)
            {
                na[i] = false;
                na[j] = false;
                break;
            }
        }

        if (na[i])
        {
            cout << i + 1 << "\n";

            return 0;
        }
    }
}

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 0 ms 596 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 141 ms 6388 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Runtime error 141 ms 6388 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 0 ms 596 KB Output isn't correct
5 Halted 0 ms 0 KB -