oj.uz

답안 #445090

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
445090 2021-07-16T11:44:11 Z leaked Plus Minus (BOI17_plusminus) C++14
100 / 100
 144 ms 12908 KB 
#include <bits/stdc++.h>

#define vec vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.begin(),x.end()
#define sz(x) (int) x.size()
#define m_p make_pair
#define pw(x) (1LL<<x)
#define fast_ioi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
auto rng=bind(uniform_int_distribution<int>(1,1000),mt19937(time(0)));
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<int,int> pii;
typedef long double ld;
const int M=1e9+7;
void paint(map<int,int> &mp,int x,int c,bool &is){
    if(mp.count(x)){
        if(mp[x]!=c) is=1;
        return;
    }
    mp[x]=c;
}
void add(int &a,int b){
    a+=b;
    if(a>=M) a-=M;
    else if(a<0) a+=M;
}
int mult(int a,int b){
    return 1ll*a*b%M;
}
int binpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1) ans=mult(ans,a);
        b>>=1;a=mult(a,a);
    }
    return ans;
}
signed main(){
    fast_ioi;
    int n,m,k;
    map<int,int>x,y;
    cin>>n>>m>>k;
    vec<array<int,3>>a(k);
    for(int i=0;i<k;i++){
        int f,s;char c;
        cin>>c>>f>>s;
        if(c=='+') a[i]={f,s,1};
        else a[i]={f,s,0};
    }
    bool k1=0,k2=0;
    for(auto &z : a){
        paint(x,z[0],(z[1]%2)^z[2],k1);
        paint(y,z[1],(z[0]%2)^z[2],k2);
    }
    if(k1 && k2) cout<<0;
    else{
    int ans=0;
    if(!k1){
        add(ans,binpow(2,n-sz(x)));
//        cerr<<binpow(2,n-sz(x))<<endl;
    }
    if(!k2){
        add(ans,binpow(2,m-sz(y)));
//        cerr<<binpow(2,m-sz(y))<<endl;
    }
    if(!k1 && !k2)add(ans,-1);
    if(!sz(x) && !sz(y)) add(ans,-1);
    cout<<ans;
    }
    return 0;
}

/*
7 3
0
1
0
1
3
5
0

*/

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct

Subtask #2
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 51 ms 2552 KB Output is correct
17 Correct 51 ms 2552 KB Output is correct
18 Correct 51 ms 2512 KB Output is correct
19 Correct 49 ms 2508 KB Output is correct
20 Correct 51 ms 2500 KB Output is correct

Subtask #3
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 51 ms 2552 KB Output is correct
17 Correct 51 ms 2552 KB Output is correct
18 Correct 51 ms 2512 KB Output is correct
19 Correct 49 ms 2508 KB Output is correct
20 Correct 51 ms 2500 KB Output is correct
21 Correct 109 ms 8372 KB Output is correct
22 Correct 0 ms 204 KB Output is correct
23 Correct 109 ms 8328 KB Output is correct
24 Correct 109 ms 8412 KB Output is correct
25 Correct 111 ms 8428 KB Output is correct
26 Correct 109 ms 10820 KB Output is correct
27 Correct 114 ms 10936 KB Output is correct
28 Correct 115 ms 11000 KB Output is correct
29 Correct 109 ms 10820 KB Output is correct
30 Correct 144 ms 12908 KB Output is correct