Submission #219698

#TimeUsernameProblemLanguageResultExecution timeMemory
219698mohamedsobhi777Linear Garden (IOI08_linear_garden)C++14
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> 

using namespace std ; 
const int N = 1e6 + 7 ; 
long long n , mod , ans ; 
string s ; 

int mv2[2] = {0 , 1} , mv1[2] = {1 , 0} ; 

long long add (long long a , long long b){
    return (a%mod + b%mod + mod) %mod ; 
}

int dp[N][4][4][4][4];

void normalize(int &a , int &b , int &A , int &B){
    int mn = min(a , b) ; 
    a-=mn ; 
    b-=mn; 
    A = max( A , a - b ) ; 
    B = max(B , b - a) ; 
}

long long solve2(int i , int a , int b , int A , int B){
    if(dp[i][a][b][A][B]!=-1)
        return dp[i][a][b][A][B] ; 
    if( a + B > 2 || b + A > 2 ) return 0 ; 
    if(i==n){
        return 1 ; 
    }
    long long ret = 0 ; 
    for(int j = 0 ; j< 2 ;j++){
        int na = a + mv1[j] ; 
        int nb = b + mv2[j] ; 
        int tmpA = A; 
        int tmpB = B; 
        normalize(na , nb , tmpA , tmpB) ; 
        char c ; 
        if(!j) c='0' ; 
        else c = '1' ; 
        ret= add(ret , solve2(i+1 , na , nb , tmpA , tmpB)) ; 
    }
    return dp[i][a][b][A][B] = ret ; 
}

int solve(int i , string ss ){
    if(i==n){
        bool ok = 1 ; 
        for(int j = 0 ; j < n ;j ++){
            int L = 0 , P = 0;
            for(int k = j ; k < n;k++){
                if(ss[k]=='L')L++ ; 
                else P++ ; 
                if(abs(L - P) > 2){
                    ok = 0 ; 
                }
            }
        }
        ans+=ok ;
        return 0 ; 
    }
    else{
        solve(i+1 , ss + "L") ; 
        solve(i+1 , ss+ "P") ; 
    }
}

int main(){
    memset(dp , -1 , sizeof dp) ; 
    ios_base::sync_with_stdio(0) ; 
    cin.tie(0) ; 
   *// freopen("in.in" , "r" , stdin) ; 
    cin>>n>>mod ; 
    cin>> s ; 
    int a = 0, b =0; 
    int A = 0, B = 0; 
    for(int i = 0 ;i < n;i++){
        if(s[i] == 'L'){
            b++ ; 
            normalize(a , b , A , B) ; 
        }else{
            a++; 
            normalize(a , b , A , B) ; 
            ans+=solve2(i+1 , a , b , A , B) ; 
           // solve(i+1 , s.substr(0 , i+1) ) ; 
        }
    }
    cout<<add(ans , 1); 
    return 0 ; 
}

Compilation message (stderr)

linear_garden.cpp: In function 'long long int solve2(int, int, int, int, int)':
linear_garden.cpp:38:14: warning: variable 'c' set but not used [-Wunused-but-set-variable]
         char c ; 
              ^
linear_garden.cpp: In function 'int main()':
linear_garden.cpp:72:4: error: no match for 'operator*' (operand type is 'std::istream {aka std::basic_istream<char>}')
    *// freopen("in.in" , "r" , stdin) ; 
    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     cin>>n>>mod ; 
     ~~~
In file included from /usr/include/c++/7/ccomplex:39:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from linear_garden.cpp:1:
/usr/include/c++/7/complex:386:5: note: candidate: template<class _Tp> std::complex<_Tp> std::operator*(const std::complex<_Tp>&, const std::complex<_Tp>&)
     operator*(const complex<_Tp>& __x, const complex<_Tp>& __y)
     ^~~~~~~~
/usr/include/c++/7/complex:386:5: note:   template argument deduction/substitution failed:
linear_garden.cpp:73:5: note:   'std::istream {aka std::basic_istream<char>}' is not derived from 'const std::complex<_Tp>'
     cin>>n>>mod ; 
     ^~~
In file included from /usr/include/c++/7/ccomplex:39:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from linear_garden.cpp:1:
/usr/include/c++/7/complex:395:5: note: candidate: template<class _Tp> std::complex<_Tp> std::operator*(const std::complex<_Tp>&, const _Tp&)
     operator*(const complex<_Tp>& __x, const _Tp& __y)
     ^~~~~~~~
/usr/include/c++/7/complex:395:5: note:   template argument deduction/substitution failed:
linear_garden.cpp:73:5: note:   'std::istream {aka std::basic_istream<char>}' is not derived from 'const std::complex<_Tp>'
     cin>>n>>mod ; 
     ^~~
In file included from /usr/include/c++/7/ccomplex:39:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from linear_garden.cpp:1:
/usr/include/c++/7/complex:404:5: note: candidate: template<class _Tp> std::complex<_Tp> std::operator*(const _Tp&, const std::complex<_Tp>&)
     operator*(const _Tp& __x, const complex<_Tp>& __y)
     ^~~~~~~~
/usr/include/c++/7/complex:404:5: note:   template argument deduction/substitution failed:
linear_garden.cpp:73:5: note:   candidate expects 2 arguments, 1 provided
     cin>>n>>mod ; 
     ^~~
In file included from /usr/include/c++/7/valarray:592:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:95,
                 from linear_garden.cpp:1:
/usr/include/c++/7/bits/valarray_after.h:404:5: note: candidate: template<class _Dom1, class _Dom2> std::_Expr<std::_BinClos<std::__multiplies, std::_Expr, std::_Expr, _Dom1, _Dom2>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const std::_Expr<_Dom1, typename _Dom1::value_type>&, const std::_Expr<_Dom2, typename _Dom2::value_type>&)
     _DEFINE_EXPR_BINARY_OPERATOR(*, __multiplies)
     ^
/usr/include/c++/7/bits/valarray_after.h:404:5: note:   template argument deduction/substitution failed:
linear_garden.cpp:73:5: note:   'std::istream {aka std::basic_istream<char>}' is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
     cin>>n>>mod ; 
     ^~~
In file included from /usr/include/c++/7/valarray:592:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:95,
                 from linear_garden.cpp:1:
/usr/include/c++/7/bits/valarray_after.h:404:5: note: candidate: template<class _Dom> std::_Expr<std::_BinClos<std::__multiplies, std::_Expr, std::_Constant, _Dom, typename _Dom::value_type>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const std::_Expr<_Dom1, typename _Dom1::value_type>&, const typename _Dom::value_type&)
     _DEFINE_EXPR_BINARY_OPERATOR(*, __multiplies)
     ^
/usr/include/c++/7/bits/valarray_after.h:404:5: note:   template argument deduction/substitution failed:
linear_garden.cpp:73:5: note:   'std::istream {aka std::basic_istream<char>}' is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
     cin>>n>>mod ; 
     ^~~
In file included from /usr/include/c++/7/valarray:592:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:95,
                 from linear_garden.cpp:1:
/usr/include/c++/7/bits/valarray_after.h:404:5: note: candidate: template<class _Dom> std::_Expr<std::_BinClos<std::__multiplies, std::_Constant, std::_Expr, typename _Dom::value_type, _Dom>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const typename _Dom::value_type&, const std::_Expr<_Dom1, typename _Dom1::value_type>&)
     _DEFINE_EXPR_BINARY_OPERATOR(*, __multiplies)
     ^
/usr/include/c++/7/bits/valarray_after.h:404:5: note:   template argument deduction/substitution failed:
linear_garden.cpp:73:5: note:   candidate expects 2 arguments, 1 provided
     cin>>n>>mod ; 
     ^~~
In file included from /usr/include/c++/7/valarray:592:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:95,
                 from linear_garden.cpp:1:
/usr/include/c++/7/bits/valarray_after.h:404:5: note: candidate: template<class _Dom> std::_Expr<std::_BinClos<std::__multiplies, std::_Expr, std::_ValArray, _Dom, typename _Dom::value_type>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const std::_Expr<_Dom1, typename _Dom1::value_type>&, const std::valarray<typename _Dom::value_type>&)
     _DEFINE_EXPR_BINARY_OPERATOR(*, __multiplies)
     ^
/usr/include/c++/7/bits/valarray_after.h:404:5: note:   template argument deduction/substitution failed:
linear_garden.cpp:73:5: note:   'std::istream {aka std::basic_istream<char>}' is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
     cin>>n>>mod ; 
     ^~~
In file included from /usr/include/c++/7/valarray:592:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:95,
                 from linear_garden.cpp:1:
/usr/include/c++/7/bits/valarray_after.h:404:5: note: candidate: template<class _Dom> std::_Expr<std::_BinClos<std::__multiplies, std::_ValArray, std::_Expr, typename _Dom::value_type, _Dom>, typename std::__fun<std::__multiplies, typename _Dom1::value_type>::result_type> std::operator*(const std::valarray<typename _Dom::value_type>&, const std::_Expr<_Dom1, typename _Dom1::value_type>&)
     _DEFINE_EXPR_BINARY_OPERATOR(*, __multiplies)
     ^
/usr/include/c++/7/bits/valarray_after.h:404:5: note:   template argument deduction/substitution failed:
linear_garden.cpp:73:5: note:   candidate expects 2 arguments, 1 provided
     cin>>n>>mod ; 
     ^~~
In file included from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:95:0,
                 from linear_garden.cpp:1:
/usr/include/c++/7/valarray:1174:1: note: candidate: template<class _Tp> std::_Expr<std::_BinClos<std::__multiplies, std::_ValArray, std::_ValArray, _Tp, _Tp>, typename std::__fun<std::__multiplies, _Tp>::result_type> std::operator*(const std::valarray<_Tp>&, const std::valarray<_Tp>&)
 _DEFINE_BINARY_OPERATOR(*, __multiplies)
 ^
/usr/include/c++/7/valarray:1174:1: note:   template argument deduction/substitution failed:
linear_garden.cpp:73:5: note:   'std::istream {aka std::basic_istream<char>}' is not derived from 'const std::valarray<_Tp>'
     cin>>n>>mod ; 
     ^~~
In file included from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:95:0,
                 from linear_garden.cpp:1:
/usr/include/c++/7/valarray:1174:1: note: candidate: template<class _Tp> std::_Expr<std::_BinClos<std::__multiplies, std::_ValArray, std::_Constant, _Tp, _Tp>, typename std::__fun<std::__multiplies, _Tp>::result_type> std::operator*(const std::valarray<_Tp>&, const _Tp&)
 _DEFINE_BINARY_OPERATOR(*, __multiplies)
 ^
/usr/include/c++/7/valarray:1174:1: note:   template argument deduction/substitution failed:
linear_garden.cpp:73:5: note:   'std::istream {aka std::basic_istream<char>}' is not derived from 'const std::valarray<_Tp>'
     cin>>n>>mod ; 
     ^~~
In file included from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:95:0,
                 from linear_garden.cpp:1:
/usr/include/c++/7/valarray:1174:1: note: candidate: template<class _Tp> std::_Expr<std::_BinClos<std::__multiplies, std::_Constant, std::_ValArray, _Tp, _Tp>, typename std::__fun<std::__multiplies, _Tp>::result_type> std::operator*(const _Tp&, const std::valarray<_Tp>&)
 _DEFINE_BINARY_OPERATOR(*, __multiplies)
 ^
/usr/include/c++/7/valarray:1174:1: note:   template argument deduction/substitution failed:
linear_garden.cpp:73:5: note:   candidate expects 2 arguments, 1 provided
     cin>>n>>mod ; 
     ^~~
linear_garden.cpp: In function 'int solve(int, std::__cxx11::string)':
linear_garden.cpp:66:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^