Submission #762847

#	Time	Username	Problem	Language	Result	Execution time	Memory
762847		ThegeekKnight16	Plus Minus (BOI17_plusminus)	C++17	100 / 100	358 ms	50176 KiB

plusminus

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;
map<int, int> CompX, DecompX, CompY, DecompY;
set<int> valsX, valsY;
array<vector<int>, MAXN> filasX, filasY;

inline int mult(int a, int b){return (a * b) % MOD;}
int exp(int x, int b)
{
    if (b < 0) return 0;
    if (b == 0) return 1;
    if (b % 2) return mult(x, exp(x, b-1));
    else return exp(mult(x, x), b/2);
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, M, K;
    cin >> N >> M >> K;

    if (N == 1 || M == 1)
    {
        cout << max(exp(2, N - K), exp(2, M - K)) << '\n';
        return 0;
    }

    if (K == 0)
    {
        cout << ((exp(2, N) + exp(2, M)) - 2) % MOD << '\n';
        return 0;
    }

    vector<tuple<char, int, int> > v(K);
    int Tipo1 = K+1, Tipo2 = K+1;
    for (int i = 0; i < K; i++)
    {
        auto &[type, x, y] = v[i];
        cin >> type >> x >> y;
        valsX.insert(x); valsY.insert(y);
        if (type == '+') Tipo1 = i;
        else Tipo2 = i;
    }
    int kX = 0, kY = 0;
    for (auto x : valsX) CompX[x] = ++kX, DecompX[kX] = x;
    for (auto y : valsY) CompY[y] = ++kY, DecompY[kY] = y;
    bool TemIntercal = true;
    for (int i = 0; i < K; i++)
    {
        auto [c1, x1, y1] = v[i];
        int dist1 = abs(x1 - get<1>(v[Tipo1])) + abs(y1 - get<2>(v[Tipo1]));
        int dist2 = abs(x1 - get<1>(v[Tipo2])) + abs(y1 - get<2>(v[Tipo2]));
        if ((Tipo1 < K && (dist1 % 2) == (c1 == '+')) || (Tipo2 < K && (dist2 % 2 == (c1 == '-')))) {TemIntercal = false; break;}
    }
    int respX = 1, respY = 1;
    for (auto [c, x, y] : v)
    {
        //Vou fingir que todos sao +, ent mudo a pos dos - por 1
        filasX[CompX[x]].push_back(y + (c == '-'));
        filasY[CompY[y]].push_back(x + (c == '-'));
    }

    //Fila no X, O(K) amortizado
    respX = exp(2, N - kX);
    for (int i = 1; i <= kX; i++)
    {
        int distBase = (filasX[i][0] % 2);
        for (int j = 1; j < (int)filasX[i].size(); j++) if ((filasX[i][j] % 2) != distBase)
        {
            respX = 0;
            break;
        }
    }

    //Fila no Y, O(K) amortizado
    respY = exp(2, M - kY);
    for (int i = 1; i <= kY; i++)
    {
        int distBase = (filasY[i][0] % 2);
        for (int j = 1; j < (int)filasY[i].size(); j++) if (filasY[i][j] % 2 != distBase)
        {
            respY = 0;
            break;
        }
    }

    // cerr << respX << " " << respY << " " << TemIntercal << '\n';

    if (!TemIntercal) cout << (respX + respY) % MOD << '\n';
    else cout << (respX + respY - 1) % MOD << '\n';
}

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