Submission #266943

#	Time	Username	Problem	Language	Result	Execution time	Memory
266943		youssefbou62	Linear Garden (IOI08_linear_garden)	C++14	0 / 100	24 ms	2560 KiB

linear_garden

        #include <bits/stdc++.h>
        #pragma GCC optimize("Ofast")
        #pragma GCC target("avx,avx2,fma")
        using namespace std;

        #define mp make_pair
        #define fi first
        #define se second
        #define all(v) v.begin(),v.end()
        #define allarr(a) a , a + n
        #define ll long long
        #define pb push_back
        #define fastio ios_base::sync_with_stdio(false) ; cin.tie(NULL); cout.tie(NULL)
        #define sz(x) (int)x.size()
        typedef pair<int, int> pi;
        typedef pair<ll,ll> pll ;
        typedef pair<int,pi> trp ;
        typedef vector<pi> vpi;
        typedef priority_queue< pi, vector <pi> , greater<pi> > spq;

        const int MAXN = 1e6+2;

        int dp[2][2][5][5][5];
        bool S[MAXN];
        int N ;
        int M ;

        void add(int& x ,int y ){
            x += y ;
            if( x >= M )x -= M ;
        }

        void solve (){
            char c ;
            for(int i = 0 ; i < N ; i++ ){
                    cin >> c ;
                    S[i]=(c=='P');
            }
            dp[0][0][2][2][2] = 1 ;
            int ans = 1 ;
            int nxt_pref ,x,y;
            for(int i = 0 ; i < N ; i++ ){
                for(int pref = -2 ; pref <= 2 ; pref++ )
                    for(int hpref = -2 ; hpref <= 2 ; hpref++ )
                        for(int lpref = -2 ; lpref <= 2 ; lpref++ ){
                            for(int choice : {0,1}){
                                        nxt_pref = pref  ;
                                        if( choice )nxt_pref++;else nxt_pref--;
                                        x = min(nxt_pref,lpref) ;
                                        y= max(nxt_pref,hpref);
                                        if( abs(hpref-lpref) > 2 || nxt_pref==3 || nxt_pref==-3||x == -3 || y == 3 || y == -3 || x == 3 )continue ;

                                        if(choice < S[i])
                                            add(dp[1][1][2+nxt_pref][2+x][2+y],dp[0][0][pref+2][lpref+2][hpref+2]);
                                        if(choice == S[i])
                                            add(dp[1][0][2+nxt_pref][2+x][2+y],dp[0][0][pref+2][lpref+2][hpref+2]);
                                        add(dp[1][1][2+nxt_pref][2+x][2+y],dp[0][1][pref+2][lpref+2][hpref+2]);
                            }

                }
                for(int pref = -2 ; pref <= 2 ; pref++ )
                    for(int hpref = -2 ; hpref <= 2 ; hpref++ )
                        for(int lpref = -2 ; lpref <= 2 ; lpref++ ){
                            for(int choice : {0,1}){
                                        dp[0][choice][pref+2][lpref+2][hpref+2]= dp[1][choice][pref+2][lpref+2][hpref+2];
                            }
                        }
                memset(dp[1],0,sizeof dp);
            }

            for(int pref = -2 ; pref <= 2 ; pref++ )
                for(int hpref = -2 ; hpref <= 2 ; hpref++ )
                    for(int lpref = -2 ; lpref <= 2 ; lpref++)
                        if( abs(hpref-lpref) <= 2 )
                            add(ans,dp[0][1][pref+2][lpref+2][hpref+2]);
         //   cout << ans << endl;

            cout << ans << endl;
        }
        int main(){
            fastio ;
          //  ifstream cin("in.in");
            cin >> N >> M  ;
            solve() ;
        }

Compilation message (stderr)

In file included from /usr/include/string.h:635,
                 from /usr/include/c++/9/cstring:42,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:48,
                 from linear_garden.cpp:1:
In function 'void* memset(void*, int, size_t)',
    inlined from 'void solve()' at linear_garden.cpp:68:23:
/usr/include/x86_64-linux-gnu/bits/string3.h:90:33: warning: 'void* __builtin___memset_chk(void*, int, long unsigned int, long unsigned int)' forming offset [2001, 3000] is out of the bounds [0, 2000] of object 'dp' with type 'int [2][2][5][5][5]' [-Warray-bounds]
   90 |   return __builtin___memset_chk (__dest, __ch, __len, __bos0 (__dest));
      |          ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
linear_garden.cpp: In function 'void solve()':
linear_garden.cpp:23:13: note: 'dp' declared here
   23 |         int dp[2][2][5][5][5];
      |             ^~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 2
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 4
• Subtask 7: 0 / 4
• Subtask 8: 0 / 4
• Subtask 9: 0 / 4
• Subtask 10: 0 / 4
• Subtask 11: 0 / 4
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5
• Subtask 22: 0 / 5
• Subtask 23: 0 / 5