Submission #933282

#	Time	Username	Problem	Language	Result	Execution time	Memory
933282		LucaIlie	Plus Minus (BOI17_plusminus)	C++17	100 / 100	92 ms	11360 KiB

plusminus

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MOD = 1e9 + 7;
unordered_map<int, int> frecvL, frecvC;

int lgPut( int x, int n ) {
    if ( n == 0 )
        return 1;

    int p = lgPut( x, n / 2 );
    p = (long long)p * p % MOD;
    if ( n % 2 == 1 )
        p = (long long)p * x % MOD;

    return p;
}

signed main() {
    int n, m, k, lin = 0, col = 0;
    bool isPossibleL = true, isPossibleC = true, isPossibleChess1 = true, isPossibleChess2 = true;

    cin >> n >> m >> k;
    for ( int i = 0; i < k; i++ ) {
        char ch;
        int s, l, c;
        cin >> ch >> l >> c;
        s = (ch == '+' ? +1 : -1);

        if ( frecvL[l] == 0 )
            lin++;
        else if ( frecvL[l] != s * (c % 2 == 0 ? 1 : -1) )
            isPossibleL = false;
        frecvL[l] = s * (c % 2 == 0 ? 1 : -1);

        if ( frecvC[c] == 0 )
            col++;
        else if ( frecvC[c] != s * (l % 2 == 0 ? 1 : -1) )
            isPossibleC = false;
        frecvC[c] = s * (l % 2 == 0 ? 1 : -1);

        if ( (l + c) % 2 == 0 && s == +1 )
            isPossibleChess1 = false;
        if ( (l + c) % 2 == 1 && s == -1 )
            isPossibleChess1 = false;

        if ( (l + c) % 2 == 0 && s == -1 )
            isPossibleChess2 = false;
        if ( (l + c) % 2 == 1 && s == +1 )
            isPossibleChess2 = false;
    }

    int ans = (isPossibleL * lgPut( 2, n - lin ) + isPossibleC * lgPut( 2, m - col ) - isPossibleChess1 - isPossibleChess2 + MOD) % MOD;
    cout << ans;

    return 0;
}

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