Submission #129901

#	Time	Username	Problem	Language	Result	Execution time	Memory
129901		Abelyan	Plus Minus (BOI17_plusminus)	C++17	100 / 100	129 ms	15084 KiB

plusminus

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define all(v) v.begin(),v.end()
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa
 
const int N=1e5+10;
const ll MOD=1e9+7;
 
vector<pair<int,char> > tox[N],syun[N];
vector<int> v1,v2;
int x[N],y[N];
char c[N];
 
ll pw(ll a,int x){
    //cout<<x<<endl;
    if (x==0)return 1;
    ll k=pw(a,x/2);
    k=(k*k)%MOD;
    if (x%2){
        return (a*k)%MOD;
    }
    return k;
}
 
int main(){
    fastio;
    srng;
    int n,m,k;
    cin>>n>>m>>k;
    ll ans;
    if (k==0){
        ans=pw(2,n)+pw(2,m)+MOD-2;
        ans%=MOD;
        cout<<ans<<endl;
        return 0;
    }
    int mn;
    char sk;
    int han=1;
    FOR(i,k){
        cin>>c[i]>>x[i]>>y[i];
        x[i]--;
        y[i]--;
        if (i==0){
            mn=(x[i]+y[i])%2;
            sk=c[i];
        }
        else if(((x[i]+y[i])%2==mn)!=(c[i]==sk)){
            han=0;
        }
 
        v1.ad(x[i]);
        v2.ad(y[i]);
    }
    sort(all(v1));
    make_unique(v1);
    sort(all(v2));
    make_unique(v2);
    FOR(i,k){
        int k1=x[i]%2,k2=y[i]%2;
        x[i]=lower_bound(all(v1),x[i])-v1.begin();
        y[i]=lower_bound(all(v2),y[i])-v2.begin();
        tox[x[i]].ad(mpr(k2,c[i]));
        syun[y[i]].ad(mpr(k1,c[i]));
    }
    //cout<<1<<endl;
    ll txans=1,syunans=1;
    FOR(i,v1.size()){
        bool bl=true;
        FOR(j,tox[i].size()){
            if ((tox[i][0].fr%2==tox[i][j].fr%2)!=(tox[i][0].sc==tox[i][j].sc))bl=false;
        }
        if (!bl)txans=0;
    }
    FOR(i,v2.size()){
        bool bl=true;
        FOR(j,syun[i].size()){
            if ((syun[i][0].fr%2==syun[i][j].fr%2)!=(syun[i][0].sc==syun[i][j].sc))bl=false;
        }
        if (!bl)syunans=0;
    }
 
    txans=txans*pw(2,n-v1.size());
    txans%=MOD;
    syunans=syunans*pw(2,m-v2.size());
    syunans%=MOD;
    ans=txans+syunans-han+MOD;
    //cout<<syunans<<endl;
    cout<<ans%MOD<<endl;
    return 0;
}

Compilation message (stderr)

plusminus.cpp: In function 'int main()':
plusminus.cpp:8:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,a) for (int i=0;i<(a);++i)
                                ^
plusminus.cpp:87:5: note: in expansion of macro 'FOR'
     FOR(i,v1.size()){
     ^~~
plusminus.cpp:8:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,a) for (int i=0;i<(a);++i)
                                ^
plusminus.cpp:89:9: note: in expansion of macro 'FOR'
         FOR(j,tox[i].size()){
         ^~~
plusminus.cpp:8:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,a) for (int i=0;i<(a);++i)
                                ^
plusminus.cpp:94:5: note: in expansion of macro 'FOR'
     FOR(i,v2.size()){
     ^~~
plusminus.cpp:8:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,a) for (int i=0;i<(a);++i)
                                ^
plusminus.cpp:96:9: note: in expansion of macro 'FOR'
         FOR(j,syun[i].size()){
         ^~~

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