Submission #453025

#	Time	Username	Problem	Language	Result	Execution time	Memory
453025		prvocislo	Plus Minus (BOI17_plusminus)	C++17	100 / 100	142 ms	8312 KiB

plusminus

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
typedef long long ll;
using namespace std;

const ll mod = 1e9 + 7;
ll pwr(ll a, ll b)
{
    if (!b) return 1;
    ll h = pwr(a, b >> 1);
    h = (h * h) % mod;
    if (b & 1) h = (h * a) % mod;
    return h;
}
int p(int x) { return x & 1; }
ll count(vector<int> &r, vector<int> &s, vector<int> &val, int maxs) // ak riadky maju pattern 1010...
{
    map<int, int> m;
    for (int i = 0; i < r.size(); i++)
    {
        int si = (1 - p(r[i])) ^ val[i];
        if (!m.count(s[i])) m[s[i]] = si;
        else if (m[s[i]] != si) return 0;
    }
    return pwr(2, maxs - m.size());
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int maxr, maxs;
    cin >> maxr >> maxs;
    int n;
    cin >> n;
    vector<int> r(n), s(n), val(n);
    int both1 = 1, both2 = 1;
    for (int i = 0; i < n; i++)
    {
        char c;
        cin >> c >> r[i] >> s[i], r[i]--, s[i]--;
        val[i] = (c == '+');
        both1 &= (p(r[i] ^ s[i]) == val[i]);
        both2 &= ((1 - p(r[i] ^ s[i])) == val[i]);
    }
    ll ans = (count(r, s, val, maxs) + count(s, r, val, maxr) - both1 - both2) % mod;
    ans = (ans + mod) % mod;
    cout << ans << "\n";
    return 0;
}

Compilation message (stderr)

plusminus.cpp: In function 'll count(std::vector<int>&, std::vector<int>&, std::vector<int>&, int)':
plusminus.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (int i = 0; i < r.size(); i++)
      |                     ~~^~~~~~~~~~

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