Submission #185303

#	Time	Username	Problem	Language	Result	Execution time	Memory
185303		Ruxandra985	Genetics (BOI18_genetics)	C++14	27 / 100	2070 ms	22788 KiB

genetics

#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;

int hsh[4110][4110];
char a[4110][4110];
int poz[4110] , p4[4110];

int convert (char c){
    if (c == 'A')
        return 0;
    if (c == 'C')
        return 1;
    if (c == 'G')
        return 2;
    return 3;
}
int interval (int l , int r , int x , int y){
    return (((hsh[x][r] - ((long long)hsh[x][l-1] * p4[r - l + 1])%MOD ))%MOD + MOD )%MOD
    == ((hsh[y][r] - ((long long)hsh[y][l-1] * p4[r - l + 1])%MOD )%MOD + MOD )%MOD;

}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , m , k , i , j , curr , etp , ok , st , dr , mid;
    fscanf (fin,"%d%d%d\n",&n,&m,&k);
    for (i=1;i<=n;i++){
        fgets (a[i] + 1 , 5000 , fin);
        for (j=1;j<=m;j++){
            hsh[i][j] = ((long long)hsh[i][j-1] * 4 + convert(a[i][j]))%MOD;
        }
    }
    p4[0] = 1;
    for (i=1;i<=m;i++)
        p4[i] = ((long long)p4[i-1] * 4)%MOD;
    for (curr = 1 ; curr <= n ; curr ++){
        /// presupunem ca curr e cel cautat
        ok = 1;

        for (i=1;i<=n;i++){
            poz[i] = 0;
        }

        for (etp = 1; etp <= k && ok ; etp++){

            for (i=1;i<=n && ok;i++){
                if (i == curr)
                    continue;
                st = 0;
                dr = m - poz[i];
                while (st <= dr){

                    mid = (st + dr)/2;
                    /// daca intervalul poz[i] ... poz[i] + mid din i = din curr
                    /// e ok, cauti mai mare

                    if (interval (poz[i] , poz[i] + mid , i , curr))
                        st = mid + 1;
                    else dr = mid - 1;

                }
                if (etp != k){
                    poz[i] += dr + 2; /// ca dr + 1 nu e ok
                    if (m - poz[i]+1 < k - etp)
                        ok = 0; /// nu
                }
                else {
                    poz[i] += dr + 2;
                    if (poz[i] > m+1 || interval (poz[i] , m , i , curr) == 0 )
                        ok = 0;
                }
            }

        }


        if (ok){
            fprintf (fout,"%d",curr);
            return 0;
        }
    }
    return 0;
}

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:28:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d%d\n",&n,&m,&k);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
genetics.cpp:30:15: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         fgets (a[i] + 1 , 5000 , fin);
         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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