Submission #629700

#	Time	Username	Problem	Language	Result	Execution time	Memory
629700		chonka	Plus Minus (BOI17_plusminus)	C++17	100 / 100	136 ms	11924 KiB

plusminus

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int MOD = 1e9 + 7 ;

ll fastpow ( ll x , ll pw ) {
    ll ret = 1 ;
    while ( pw > 0 ) {
        if ( ( pw % 2 ) == 0 ) {
            x = ( x * x ) % MOD ;
            pw /= 2 ;
        }
        else {
            ret = ( ret * x ) % MOD ;
            -- pw ;
        }
    }
    return ret ;
}

int n , m , k ;
map < int , int > wr , wc ;

void solve ( ) {
    cin >> n >> m >> k ;
    int rem_rows = n , rem_cols = m ;
    bool bad_row = false , bad_col = false ;
    bool ch1 = true , ch2 = true ;
    for ( int i = 1 ; i <= k ; ++ i ) {
        char c ; cin >> c ;
        int val = ( c == '+' ) ;
        int x , y ; cin >> x >> y ;
        int hh_row = ( 1 << ( ( y % 2 ) ^ val ) ) ;
        if ( wr[ x ] == 0 ) { -- rem_rows ; }
        wr[ x ] |= hh_row ;
        if ( wr[ x ] == 3 ) { bad_row = true ; }

        int hh_col = ( 1 << ( ( x % 2 ) ^ val ) ) ;
        if ( wc[ y ] == 0 ) { -- rem_cols ; }
        wc[ y ] |= hh_col ;
        if ( wc[ y ] == 3 ) { bad_col = true ; }

        if ( ( x + y ) % 2 == 0 ) {
            if ( val == 1 ) { ch1 = false ; }
            else { ch2 = false ; }
        }
        else {
            if ( val == 1 ) { ch2 = false ; }
            else { ch1 = false ; }
        }
    }
    ll ans = 0 ;
    if ( bad_row == false ) {
        ans += fastpow ( 2 , rem_rows ) ;
    }
    if ( bad_col == false ) {
        ans += fastpow ( 2 , rem_cols ) ;
    }
    if ( bad_row == false && bad_col == false ) {
        if ( ch1 == true ) { ans = ( ans - 1 + MOD ) % MOD ; }
        if ( ch2 == true ) { ans = ( ans - 1 + MOD ) % MOD ; }
    }
    cout << ans << "\n" ;
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; // cin >> t ; 
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}

• Subtask 1: 12 / 12
• Subtask 2: 42 / 42
• Subtask 3: 46 / 46