Submission #1116001

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116001		Thanhs	Plus Minus (BOI17_plusminus)	C++17	0 / 100	1 ms	336 KiB

plusminus

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

#define name "TENBAI"
#define fi first
#define se second
#define int long long
#define endl '\n'
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))

mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}

const int NM = 1e5 + 5;
const int mod = 1e9 + 7;

struct mi
{
    int v;
    mi() : v(0){}
    mi(int _v) : v(_v)
    {
        if (v >= mod)
            v -= mod;
    }
    int inv() const
    {
        int t = mod - 2, res = 1, tt = v;
        while (t)
        {
            if (t & 1)
                res = 1ll * res * tt % mod;
            tt = 1ll * tt * tt % mod;
            t >>= 1;
        }
        return res;
    }
    mi operator+(const mi& o)
    {
        return mi(v + o.v);
    }
    mi operator-(const mi& o)
    {
        return mi(v + mod - o.v);
    }
    mi operator*(const mi& o)
    {
        return mi(1ll * v * o.v % mod);
    }
    mi operator/(const mi& o)
    {
        return mi(1ll * v * o.inv() % mod);
    }
    mi& operator+=(const mi &o)
    {
        v += o.v;
        if (v >= mod)
            v -= mod;
        return *this;
    }
    mi& operator-=(const mi &o)
    {
        v += mod - o.v;
        if (v >= mod)
            v -= mod;
        return *this;
    }
    mi& operator*=(const mi& o)
    {
        v = 1ll * v * o.v % mod;
        return *this;
    }
    mi& operator/=(const mi& o)
    {
        v = 1ll * v * o.inv() % mod;
        return *this;
    }
}dp[2], ans;

pair<int, int> a[NM];
int n, m, k;
map<int, int> R, C;

mi bp(mi x, int y)
{
    mi res = 1;
    while (y)
    {
        if (y & 1)
            res *= x;
        x *= x;
        y >>= 1;
    }
    return res;
}

void chet()
{
    cout << 0;
    exit(0);
}

void calc(map<int, int>& mp, int mx)
{
    if (mp.count(1))
        dp[mp[1]] = 1, dp[mp[1] ^ 1] = 0;
    else
        dp[0] = dp[1] = 1;
    int pr = 1;
    for (auto t : mp)
    {
        if (t.fi == 1)
            continue;
        if (pr < t.fi - 1)
            dp[0] = dp[1] = (dp[0] + dp[1]) * bp(2, t.fi - 1 - pr);
        dp[t.se] = dp[0] + dp[1];
        dp[t.se ^ 1] = 0;
        pr = t.fi;
    }
    if (pr < mx)
        dp[0] = dp[1] = (dp[1] + dp[0]) * bp(2, mx - pr - 1);
    ans += dp[0] + dp[1];
}

bool check(map<int, int>& mp, bool x)
{
    for (auto t : mp)
        if (x != t.se)
            return 0;
    return 1;
}

void solve()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= k; i++)
    {
        char c;
        cin >> c >> a[i].fi >> a[i].se;
        int t = (a[i].fi & 1) ^ (a[i].se & 1) ^ (c == '+');
        if (R.find(a[i].fi) == R.end())
            R[a[i].fi] = t;
        else if (R[a[i].fi] != t)
            chet();
        if (C.find(a[i].se) == C.end())
            C[a[i].se] = t;
        else if (C[a[i].se] != t)
            chet();
    }
    // calc(R, n);
    ans += bp(2, n - (int)(R.size()));
    // calc(C, m);
    ans += bp(2, m - (int)(C.size()));
    ans = ans - (check(C, 0) && check(R, 0));
    ans = ans - (check(C, 1) && check(R, 1));
    cout << ans.v;
}

signed main()
{
    if (fopen("in.txt", "r")) 
    {
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    }
    else if (fopen(name".inp", "r"))
    {
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int tc = 1; 
    // cin >> tc;
    while (tc--)
        solve();
}

Compilation message (stderr)

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

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