oj.uz

답안 #790636

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
790636 2023-07-23T02:56:55 Z 1075508020060209tc Plus Minus (BOI17_plusminus) C++14
100 / 100
 148 ms 28948 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;
#define int long long
int mod=1e9+7;
int qpow(int x,int t){
if(t==0){return 1;}
if(t%2==1){return x*qpow(x,t-1)%mod;}
int xx=qpow(x,t/2);
return xx*xx%mod;
}
int H;int W;int n;
int ar[200005];int br[200005];int vl[200005];
vector<pair<int,int>>rw[300005];
vector<pair<int,int>>clm[300005];
int oar[200005];
int obr[200005];
int ovl[200005];

void lisanhua(){

vector<int>vc;
for(int i=1;i<=n;i++){
    vc.push_back(ar[i]);
    vc.push_back(br[i]);
}
sort(vc.begin(),vc.end());
for(int i=1;i<=n;i++){
    ar[i]=1+lower_bound(vc.begin(),vc.end(),ar[i])-vc.begin();
    br[i]=1+lower_bound(vc.begin(),vc.end(),br[i])-vc.begin();
    rw[ar[i]].push_back({obr[i],vl[i]});
    clm[br[i]].push_back({oar[i],vl[i]});
}
}
int ans;
void rwcount(){
int cnt=0;
for(int i=1;i<=n+n;i++){
    if(rw[i].size()==0){continue;}
    cnt++;
    int typ=(rw[i][0].first+rw[i][0].second)%2;
    for(int j=1;j<rw[i].size();j++){
        int v=(rw[i][j].first+rw[i][j].second)%2;
        if(v!=typ){return;}
    }
}
ans+=qpow(2,H-cnt);
}

void clmcount(){
int cnt=0;
for(int i=1;i<=n+n;i++){
    if(clm[i].size()==0){continue;}
    cnt++;
    int typ=(clm[i][0].first+clm[i][0].second)%2;
    for(int j=1;j<clm[i].size();j++){
        int v=(clm[i][j].first+clm[i][j].second)%2;
        if(v!=typ){return;}
    }
}
ans+=qpow(2,W-cnt);


}

signed main()
{
    cin>>H>>W>>n;
    for(int i=1;i<=n;i++){
        char c;
        cin>>c>>ar[i]>>br[i];
        if(c=='+'){vl[i]=1;}else{
            vl[i]=0;
        }
        oar[i]=ar[i];
        obr[i]=br[i];
        ovl[i]=vl[i];
    }
    lisanhua();
    ans=0;
    rwcount();
    clmcount();
    if(n==0){
        cout<<(ans-2+mod)%mod;return 0;
    }
 //   cout<<ans<<" ";
    int ok=1;
    for(int i=1;i<=n;i++){
        int typ=(oar[i]+obr[i]+ovl[i])%2;
        int ch=(oar[1]+obr[1]+ovl[1])%2;
        if(ch!=typ){
            ok=0;
        }
      //  cout<<ch<<" "<<typ<<endl;
    }
    if(ok){
        ans--;
        ans+=mod;
        ans%=mod;
    }
    cout<<ans<<endl;
}

Compilation message

plusminus.cpp: In function 'void rwcount()':
plusminus.cpp:43:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int j=1;j<rw[i].size();j++){
      |                 ~^~~~~~~~~~~~~
plusminus.cpp: In function 'void clmcount()':
plusminus.cpp:57:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int j=1;j<clm[i].size();j++){
      |                 ~^~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14404 KB Output is correct
2 Correct 9 ms 14420 KB Output is correct
3 Correct 8 ms 14324 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14404 KB Output is correct
6 Correct 8 ms 14404 KB Output is correct
7 Correct 8 ms 14404 KB Output is correct
8 Correct 8 ms 14340 KB Output is correct
9 Correct 8 ms 14420 KB Output is correct
10 Correct 8 ms 14324 KB Output is correct
11 Correct 10 ms 14540 KB Output is correct
12 Correct 8 ms 14404 KB Output is correct
13 Correct 8 ms 14392 KB Output is correct
14 Correct 9 ms 14536 KB Output is correct
15 Correct 9 ms 14540 KB Output is correct
16 Correct 84 ms 26112 KB Output is correct
17 Correct 84 ms 26032 KB Output is correct
18 Correct 84 ms 25972 KB Output is correct
19 Correct 85 ms 26028 KB Output is correct
20 Correct 85 ms 25908 KB Output is correct

Subtask #3
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14404 KB Output is correct
2 Correct 9 ms 14420 KB Output is correct
3 Correct 8 ms 14324 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14404 KB Output is correct
6 Correct 8 ms 14404 KB Output is correct
7 Correct 8 ms 14404 KB Output is correct
8 Correct 8 ms 14340 KB Output is correct
9 Correct 8 ms 14420 KB Output is correct
10 Correct 8 ms 14324 KB Output is correct
11 Correct 10 ms 14540 KB Output is correct
12 Correct 8 ms 14404 KB Output is correct
13 Correct 8 ms 14392 KB Output is correct
14 Correct 9 ms 14536 KB Output is correct
15 Correct 9 ms 14540 KB Output is correct
16 Correct 84 ms 26112 KB Output is correct
17 Correct 84 ms 26032 KB Output is correct
18 Correct 84 ms 25972 KB Output is correct
19 Correct 85 ms 26028 KB Output is correct
20 Correct 85 ms 25908 KB Output is correct
21 Correct 124 ms 27084 KB Output is correct
22 Correct 8 ms 14352 KB Output is correct
23 Correct 118 ms 27084 KB Output is correct
24 Correct 118 ms 27060 KB Output is correct
25 Correct 122 ms 27184 KB Output is correct
26 Correct 113 ms 26552 KB Output is correct
27 Correct 113 ms 26548 KB Output is correct
28 Correct 121 ms 26700 KB Output is correct
29 Correct 112 ms 26640 KB Output is correct
30 Correct 148 ms 28948 KB Output is correct