Submission #228296

#	Time	Username	Problem	Language	Result	Execution time	Memory
228296		Ruxandra985	Snake Escaping (JOI18_snake_escaping)	C++14	75 / 100	2086 ms	26104 KiB

snake_escaping

#include <bits/stdc++.h>
#define DIMN 2000000
using namespace std;
int sol , nr;
int n;
char s[30];
char v[2000000];
int bits[DIMN] , dp0[DIMN] , dp1[DIMN];
void solve_brut (int poz){

    if (poz == n + 1){

        sol += v[nr] - '0';
        return;

    }

    if (s[poz] != '?'){
        nr = nr * 2 + (s[poz] - '0');
        solve_brut (poz + 1);
        nr /= 2;
    }
    else {
        nr = nr * 2;

        solve_brut(poz + 1); /// pui 0

        nr++;

        solve_brut(poz + 1); /// pui 1

        nr /= 2;
    }

}

int calcul (int x){
    int nr = 0;

    while (x){
        nr += (x % 2);
        x /= 2;
    }

    return nr;


}

int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int q , i , c0 , c1 , c2 , nr0 , nr1 , nr2 , j , mask , stot = 0;
    fscanf (fin,"%d%d\n",&n,&q);

    fgets (v , (1 << n) + 10 , fin);

    /// precalculari ???

    /// cum il fac pe dp0

    for (i = 0 ; i < (1 << n) ; i++){

        bits[i] = calcul(i);

        dp1[i] = dp0[i] = v[i] - '0';

        stot += v[i] - '0';

    }

    for (i = 0 ; i < n ; i++){
        for (j = 0 ; j < ( 1 << n ) ; j++){

            if ((j & (1 << i)) == 0)
                dp0[j] += dp0[j ^ (1 << i)];
            else dp1[j] += dp1[j ^ (1 << i)];

        }
    }


    for (;q;q--){
        fgets (s + 1 , n + 10 , fin);

        c0 = c1 = c2 = 0;
        nr1 = nr0 = nr2 = 0;
        for (i = 1 ; i <= n ; i++){

            c0 *= 2;
            c1 *= 2;
            c2 *= 2;

            if (s[i] == '1')
                c1++ , nr1++;
            else if (s[i] == '0')
                c0++ , nr0++;
            else
                c2++ , nr2++;

            /// numar cati de 0 , cati de 1 si cati de ? sunt + unde sunt
        }

        sol = 0;

        if (nr0 == min(nr0 , min(nr1 , nr2))){ /// 0 apare de cele mai putine ori
            for ( i = c0 ; true ; i = ( (i - 1) & c0) ){

                mask = (i | c1);
                /// eu vreau ca bitii din mask sa fie FIXATI

                if (bits[i] % 2 == 1)
                    sol -= dp0[mask];
                else sol += dp0[mask];

                if (i == 0)
                    break;

            }

        }
        else if (nr1 == min(nr0 , min(nr1 , nr2))){ /// 1 apare de cele mai putine ori
            for ( i = c1 ; true ; i = ( (i - 1) & c1) ){

                mask = (i | c2);
                /// eu vreau ca bitii din mask sa fie FIXATI

                if (bits[i] % 2 == 1)
                    sol -= dp1[mask];
                else sol += dp1[mask];

                if (i == 0)
                    break;

            }
        }
        else { /// ? apare de cele mai putine ori
            /// pt cazul asta poti sa faci brut
            solve_brut (1);
        }

        sol = max(sol , -sol);
        fprintf (fout,"%d\n" , sol);

    }

    return 0;
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:55:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d\n",&n,&q);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:57:11: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     fgets (v , (1 << n) + 10 , fin);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:85:15: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         fgets (s + 1 , n + 10 , fin);
         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 53 / 53
• Subtask 5: 0 / 25