Submission #1276336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276336		Ludissey	Plus Minus (BOI17_plusminus)	C++20	100 / 100	240 ms	24492 KiB

plusminus

#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define int long long
using namespace std;

const int MOD=1e9+7;

int fast_pow(int x, int p){
    if(p==0) return 1;
    if(p%2) return (fast_pow(x,p-1)*x)%MOD;
    else {
        int fp=fast_pow(x,p/2);
        return (fp*fp)%MOD;
    }
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n,m,k; cin >> n >> m >> k;
    set<int> st_rows;
    set<int> st_columns;
    vector<int> rows,columns;
    bool canROW=true;
    bool canCOLUMN=true;
    
    
    unordered_map<int,int> rowsI,columnsI;
    vector<pair<pair<int,int>,bool>> a(k);
    for (int i = 0; i < k; i++)
    {
        char c; cin >> c;
        if(c=='-') a[i].second=false;
        else a[i].second=true;
        cin >> a[i].first.first >> a[i].first.second;
        st_rows.insert(a[i].first.first);
        st_columns.insert(a[i].first.second);
    }
    int _j=0;
    for (auto u : st_rows) {
        rows.push_back(u);
        rowsI[u]=_j++;
    }
    _j=0;
    for (auto u : st_columns) {
        columns.push_back(u);
        columnsI[u]=_j++;
    }
    vector<int> rowsID(sz(rows),-1),columnsID(sz(columns),-1);

    for (int i = 0; i < k; i++)
    {
        int ri=(a[i].first.second+a[i].second)%2;
        int ci=(a[i].first.first+a[i].second)%2;
        if(rowsID[rowsI[a[i].first.first]]==-1) rowsID[rowsI[a[i].first.first]]=ri;
        if(rowsID[rowsI[a[i].first.first]]!=ri) canROW=false; 

        if(columnsID[columnsI[a[i].first.second]]==-1) columnsID[columnsI[a[i].first.second]]=ci;
        if(columnsID[columnsI[a[i].first.second]]!=ci) canCOLUMN=false; 
    }
    int sm=0;
    if(canROW){
        int rowSM=1;
        int l=0;
        for (int i = 0; i < sz(rows); i++)
        {
            rowSM=(rowSM*fast_pow(2,rows[i]-l-1))%MOD;
            l=rows[i];
        }
        rowSM=(rowSM*fast_pow(2,n-l))%MOD;
        sm+=rowSM;
    }
    if(canCOLUMN){
        int colSM=1;
        int l=0;
        for (int i = 0; i < sz(columns); i++)
        {
            colSM=(colSM*fast_pow(2,columns[i]-l-1))%MOD;
            l=columns[i];
        }
        colSM=(colSM*fast_pow(2,m-l))%MOD;
        sm+=colSM;
        sm%=MOD;
    }
    if(canROW&&canCOLUMN){
        bool cris1=true;
        bool cris2=true;
        for (int i = 0; i < sz(rows); i++)
        {
            cris1=cris1&&((rows[i]+rowsID[i])%2);
            cris2=cris2&&((rows[i]+rowsID[i])%2==0);
        }
        sm=(sm-cris1-cris2+MOD)%MOD;
    }
    cout << sm << "\n";
    return 0;
}

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