Submission #1116443

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116443		vjudge1	Plus Minus (BOI17_plusminus)	C++17	100 / 100	206 ms	19392 KiB

plusminus

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define el cout << '\n'
#define f1(i,n) for(int i=1;i<=n;i++)
#define __file_name "TEST"
using namespace std;
const ll maxn = 1e6+5, inf=1e18, mod=1e9+7;

ll powmod(ll base, ll exp){
    ll res = 1;
    while(exp){
        if(exp & 1) res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

struct Cell{
    int x, y;
    char s;
};

ll n,m,k,pp = -1, ans;
int flag = 2;
vector<Cell> cells;
map<int, char> srow, scol;
map<pair<int,int>, char> S;
int crow, ccol;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    if(fopen(__file_name ".inp", "r")){
        freopen(__file_name ".inp","r",stdin);
        freopen(__file_name ".out","w",stdout);
    }
    // code here
    cin >> n >> m >> k;
    if(n == 1 || m == 1){
        cout << powmod(2, n + m - 1 - k);
        return 0;
    }
    f1(i,k){
        Cell tmp;
        cin >> tmp.s >> tmp.x >> tmp.y;
        cells.push_back(tmp);
        // pp: parity of symbol +
        int parity = (tmp.x + tmp.y) & 1;
        if(tmp.s == '-') parity ^= 1;
        if(pp == -1){
            pp = parity;
        }else if(pp != parity){
            flag = false;
        }
        flag = min(flag, 1);
    }
    // flag = true -> it is possible to exist
    // no two consecutive cells having same symbol
    bool erow = false, ecol = false, prow = true, pcol = true;
    for(Cell c: cells){
        // row
        char frow = (c.y & 1 ? c.s : '+' + '-' - c.s);
        if(srow.find(c.x) != srow.end()){
            if(frow != srow[c.x]) prow = false;
        }else crow++;
        erow |= (S.find({c.x-1, c.y}) != S.end() && S[{c.x-1, c.y}] == c.s);
        erow |= (S.find({c.x+1, c.y}) != S.end() && S[{c.x+1, c.y}] == c.s);
//        erow |= (srow.find(c.x - 1) != srow.end() && srow[c.x-1] == frow);
//        erow |= (srow.find(c.x + 1) != srow.end() && srow[c.x+1] == frow);
        srow[c.x] = frow;
        // column
        char fcol = (c.x & 1 ? c.s : '+' + '-' - c.s);
        if(scol.find(c.y) != scol.end()){
            if(fcol != scol[c.y]) pcol = false;
        }else ccol++;
        ecol |= (S.find({c.x, c.y-1}) != S.end() && S[{c.x, c.y-1}] == c.s);
        ecol |= (S.find({c.x, c.y+1}) != S.end() && S[{c.x, c.y+1}] == c.s);
//        ecol |= (scol.find(c.y - 1) != scol.end() && scol[c.y-1] == fcol);
//        ecol |= (scol.find(c.y + 1) != scol.end() && scol[c.y+1] == fcol);
        scol[c.y] = fcol;
        S[{c.x, c.y}] = c.s;
    }
    if(erow && ecol) return cout << 0, 0;
//    if(!prow && erow) return cout << 0, 0;
//    if(!pcol && ecol) return cout << 0, 0;
    ans = flag;
    // cerr << erow << ' ' << ecol << ' ' << prow << ' ' << pcol << '\n';
    if(!ecol && prow){
        ans = (ans + powmod(2, n - crow) - flag + mod) % mod;
    }
    if(!erow && pcol) ans = (ans + powmod(2, m - ccol) - flag + mod) % mod;
    cout << ans;
    return 0;
}

Compilation message (stderr)

plusminus.cpp: In function 'int main()':
plusminus.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen(__file_name ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plusminus.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen(__file_name ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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