Submission #129612

#	Time	Username	Problem	Language	Result	Execution time	Memory
129612		SamAnd	Plus Minus (BOI17_plusminus)	C++17	0 / 100	2 ms	376 KiB

plusminus

#include <bits/stdc++.h>
using namespace std;
const int M = 1000000007, N = 1003;

int ast(int x, int n)
{
    if (n == 0)
        return 1;
    if (n % 2 == 0)
    {
        int y = ast(x, n / 2);
        return (y * 1LL * y) % M;
    }
    else
    {
        int y = ast(x, n - 1);
        return (x * 1LL * y) % M;
    }
}

int ans0, ans1;

int n, m, k;

map<int, vector<int> >  sp0, sm0;
set<int> z1, z2;
set<int> sp, sm;

int dp[N][2][2];
int main()
{
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin >> n >> m >> k;
    for (int i = 0; i < k; ++i)
    {
        char ty;
        int x, y;
        cin >> ty >> x >> y;
        if (ty == '-')
            sm0[x].push_back(y);
        else
            sp0[x].push_back(y);
        if (x % 2 == 1)
        {
            if (ty == '+')
                sp.insert(y);
            else
                sm.insert(y);
        }
        else
        {
            if (ty == '-')
                sp.insert(y);
            else
                sm.insert(y);
        }
    }

    // count ans0
    ans0 = 1;
    for (map<int, vector<int> >::iterator it = sp0.begin(); it != sp0.end(); ++it)
    {
        for (int i = 0; i < it->second.size(); ++i)
        {
            if (it->second[i] % 2 == 0)
                z1.insert(it->first);
            else
                z2.insert(it->first);
        }
    }
    for (map<int, vector<int> >::iterator it = sm0.begin(); it != sm0.end(); ++it)
    {
        for (int i = 0; i < it->second.size(); ++i)
        {
            if (it->second[i] % 2 == 1)
                z1.insert(it->first);
            else
                z2.insert(it->first);
        }
    }
    for (set<int>::iterator it = z1.begin(); it != z1.end(); ++it)
    {
        if (z2.find((*it)) != z2.end())
        {
            ans0 = 0;
            break;
        }
    }
    //ans0 = (ans0 * 1LL * ast(2, n - z1.size() - z2.size()));
    //count ans1
    if (sm.find(1) != sm.end())
        dp[1][0][0] = 1;
    else if (sp.find(1) != sp.end())
        dp[1][1][0] = 1;
    else
    {
        dp[1][0][0] = 1;
        dp[1][1][0] = 1;
    }
    for (int i = 1; i < m; ++i)
    {
        if (sm.find(i + 1) != sm.end())
        {
            dp[i + 1][0][1] += dp[i][0][0];
            //dp[i + 1][1][0] += dp[i][0][0];

            dp[i + 1][0][0] += dp[i][1][0];
            //dp[i + 1][1][1] += dp[i][1][0];

            dp[i + 1][0][1] += dp[i][0][1];
            //dp[i + 1][1][1] += dp[i][0][1];

            dp[i + 1][0][1] += dp[i][1][1];
            //dp[i + 1][1][1] += dp[i][1][1];
        }
        else if (sp.find(i + 1) != sp.end())
        {
            //dp[i + 1][0][1] += dp[i][0][0];
            dp[i + 1][1][0] += dp[i][0][0];

            //dp[i + 1][0][0] += dp[i][1][0];
            dp[i + 1][1][1] += dp[i][1][0];

            //dp[i + 1][0][1] += dp[i][0][1];
            dp[i + 1][1][1] += dp[i][0][1];

            //dp[i + 1][0][1] += dp[i][1][1];
            dp[i + 1][1][1] += dp[i][1][1];
        }
        else
        {
            dp[i + 1][0][1] += dp[i][0][0];
            dp[i + 1][1][0] += dp[i][0][0];

            dp[i + 1][0][0] += dp[i][1][0];
            dp[i + 1][1][1] += dp[i][1][0];

            dp[i + 1][0][1] += dp[i][0][1];
            dp[i + 1][1][1] += dp[i][0][1];

            dp[i + 1][0][1] += dp[i][1][1];
            dp[i + 1][1][1] += dp[i][1][1];
        }
        dp[i + 1][0][0] %= M;
        dp[i + 1][0][1] %= M;
        dp[i + 1][1][0] %= M;
        dp[i + 1][1][1] %= M;
    }
    ans1 = (dp[m][1][1] + dp[m][0][1]) % M;
    for (int y = 1; y <= m; ++y)
    {
        if (sm.find(y) != sm.end() && sp.find(y) != sp.end())
            ans1 = 0;
    }
    cout << (ans0 + ans1) % M << endl;
    return 0;
}

Compilation message (stderr)

plusminus.cpp: In function 'int main()':
plusminus.cpp:64:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < it->second.size(); ++i)
                         ~~^~~~~~~~~~~~~~~~~~~
plusminus.cpp:74:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < it->second.size(); ++i)
                         ~~^~~~~~~~~~~~~~~~~~~

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