Submission #62720

#	Time	Username	Problem	Language	Result	Execution time	Memory
62720		eriksuenderhauf	Genetics (BOI18_genetics)	C++11	100 / 100	706 ms	21752 KiB

genetics

#include <bits/stdc++.h>
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pll pair<long long,long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 5e3 + 5;
const double eps = 1e-9;
using namespace std;
char str[MAXN][MAXN];
bitset<MAXN> a[MAXN][4];
int cnt[MAXN][4];
int vis[MAXN][MAXN];
pll hsh[MAXN], ans[MAXN];

int go(char c)
{
    if (c == 'A') return 0;
    else if (c == 'C') return 1;
    else if (c == 'G') return 2;
    else if (c == 'T') return 3;
}

int main()
{
    int n, m, k;
    ni(n), ni(m), ni(k);
    pll sm;
    for (int i = 0; i < n; i++)
    {
        scanf("%s", str[i]);
        hsh[i] = {rand() % MOD, rand() % MOD};
        sm = {(sm.fi+hsh[i].fi)%MOD,(sm.se+hsh[i].se)%MOD};
        /*for (int j = 0; j < m; j++)
        {
            int cur = go(str[i][j]);
            a[i][cur][j] = 1;
            cnt[j][cur]++;
            vis[i][j] = -1;
        }
        for (int j = m; j < n; j++)
            vis[i][j] = -1;*/
    }
    /*for (int i = n - 1; i >= 0; i--)
    {
        int tmp = 0;
        for (int j = 0; j < m; j++)
            tmp += n - cnt[j][go(str[i][j])];
        if (tmp != k * (n - 1))
            continue;
        int fl = 0;
        for (int j = n - 1; j >= 0; j--)
        {
            if (i == j)
                continue;
            int val = 0;
            if (vis[i][j] != -1)
                val = vis[i][j];
            else
            {
                for (int b = 0; b < 4; b++)
                {
                    val += (a[i][b] ^ a[j][b]).count();
                    if (val > 2 * k)
                        break;
                }
                vis[i][j] = val;
                vis[j][i] = val;
            }
            if (val != 2 * k)
            {
                fl = 1;
                break;
            }
        }
        if (fl)
            continue;
        return !pri(i + 1);
    }*/
    for (int i = 0; i < m; i++)
    {
        pll tmp[4];
        for (int j = 0; j < n; j++)
            tmp[go(str[j][i])] = {(tmp[go(str[j][i])].fi+hsh[j].fi)%MOD,(tmp[go(str[j][i])].se+hsh[j].se)%MOD};
        for (int j = 0; j < n; j++)
            ans[j] = {(ans[j].fi+sm.fi-tmp[go(str[j][i])].fi+MOD)%MOD,(ans[j].se+sm.se-tmp[go(str[j][i])].se+MOD)%MOD};
    }
    for (int i = 0; i < n; i++)
        if (ans[i] == mp(k*((sm.fi-hsh[i].fi+MOD)%MOD)%MOD,k*((sm.se-hsh[i].se+MOD)%MOD)%MOD))
            return !pri(i + 1);
    return 0;
}

Compilation message (stderr)

genetics.cpp: In function 'int go(char)':
genetics.cpp:37:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
genetics.cpp: In function 'int main()':
genetics.cpp:42:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     ni(n), ni(m), ni(k);
                 ^
genetics.cpp:42:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
genetics.cpp:42:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
genetics.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", str[i]);
         ~~~~~^~~~~~~~~~~~~~

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