oj.uz

답안 #588349

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
588349 2022-07-03T08:23:25 Z Huy Plus Minus (BOI17_plusminus) C++17
100 / 100
 209 ms 39240 KB 
/// no sound please
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define pic pair<int,char>
#define fi first
#define se second
/*#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")*/
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ldb = long double;
const ll N = (int)1e9 + 1;
const int maxN = (int)3e5 + 5;
const int mod = 1e9 + 7;
//const int mod = 998244353;
const ll infty = 1e18 + 7;
const int base = (int)4e5;

void InputFile()
{
    //freopen("IELTS.inp","r",stdin);
    //freopen("IELTS.out","w",stdout);
    //freopen("test.out","r",stdin);
}

void FastInput()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}

int power(int a,int b)
{
    if(b == 0) return 1;
    int t = power(a,b/2);
    if(b % 2)
    {
        return t * t % mod * a % mod;
    }
    return t * t % mod;
}

int m,n,k;
char spin[maxN];
int x[maxN];
int y[maxN];
vector<pic> on_row[maxN];
vector<pic> on_col[maxN];
vector<int> old_col;
map<int,int> new_col;
int cnt_col;
vector<int> vc;
vector<int> old_row;
map<int,int> new_row;
int cnt_row;


void Read()
{
    cin >> m >> n >> k;
    for(int i = 1; i <= k; i++)
    {
        cin >> spin[i] >> x[i] >> y[i];
    }
}

void Renumb_row()
{
    vc.clear();
    for(int i = 1; i <= k; i++)
    {
        vc.push_back(x[i]);
    }
    sort(vc.begin(),vc.end());
    //old_row.push_back(0);
    int old = -1;
    int now = 0;
    for(int i : vc)
    {
        if(i > old)
        {
            old = i;
            now++;
            old_row.push_back(i);
        }
        new_row[old] = now;
    }
    cnt_row = now;
    for(int i = 1; i <= k; i++)
    {
        on_row[new_row[x[i]]].push_back({y[i],spin[i]});
    }
}

void Renumb_col()
{
    vc.clear();
    for(int i = 1; i <= k; i++)
    {
        vc.push_back(y[i]);
    }
    sort(vc.begin(),vc.end());
    //old_col.push_back(0);
    int old = -1;
    int now = 0;
    for(int i : vc)
    {
        if(i > old)
        {
            old = i;
            now++;
            old_col.push_back(i);
        }
        new_col[old] = now;
    }
    cnt_col = now;
    for(int i = 1; i <= k; i++)
    {
        on_col[new_col[y[i]]].push_back({x[i],spin[i]});
    }
}

void Solve()
{
    old_col.push_back(0);
    old_row.push_back(0);
    if(k > 0) Renumb_col();
    if(k > 0) Renumb_row();

    int res = 0;

    int su = 1;
    for(int i = 1; i <= cnt_col; i++)
    {
        su *= power(2,old_col[i]-old_col[i-1]-1);
        su %= mod;
        char t[2];
        t[0] = t[1] = '?';
        for(pic tmp : on_col[i])
        {
            if(t[tmp.fi%2] == '?')
            {
                t[tmp.fi%2] = tmp.se;
                t[1-tmp.fi%2] = '+' + '-' - tmp.se;
            }
            else if(t[tmp.fi%2] != tmp.se)
            {
                su = 0;
                break;
            }
        }
    }

    su *= power(2,n-old_col[cnt_col]);
    su %= mod;
    res += su;
    res %= mod;
    //cout << su <<'\n';

    su = 1;
    for(int i = 1; i <= cnt_row; i++)
    {
        su *= power(2,old_row[i]-old_row[i-1]-1);
        su %= mod;
        char t[2];
        t[0] = t[1] = '?';
        for(pic tmp : on_row[i])
        {
            if(t[tmp.fi%2] == '?')
            {
                t[tmp.fi%2] = tmp.se;
                t[1-tmp.fi%2] = '+' + '-' - tmp.se;
            }
            else if(t[tmp.fi%2] != tmp.se)
            {
                su = 0;
                break;
            }
        }
    }
    su *= power(2,m-old_row[cnt_row]);
    su %= mod;
    res += su;
    res %= mod;
    //cout << su <<'\n';

    int down = 0;
    if(k == 0) down = 2;
    else
    {
        char t[2];
        t[0] = t[1] = '?';
        down = 1;
        for(int i = 1; i <= k; i++)
        {
            if(t[(x[i]+y[i])%2] == '?')
            {
                t[(x[i]+y[i])%2] = spin[i];
                t[1-(x[i]+y[i])%2] = '+' + '-' - spin[i];
            }
            else if(t[(x[i]+y[i])%2] != spin[i])
            {
                down = 0;
                break;
            }
        }
    }
    //cout <<"dark";return;
    res = res - down;
    if(res < 0) res += mod;
    cout << res;
}

void Debug()
{

}


int32_t main()
{
    FastInput();
    //InputFile();
    //int sub_type;
    //cin >> sub_type;
    //Sieve();
    //Prepare();
    int test;
    //cin >> test;
    test = 1;
    while(test--)
        //for(int prc = 1; prc <= test; prc++)
    {
        Read();
        Solve();
        //Debug();
    }
}

Subtask #1
12.0 / 12.0

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

Subtask #2
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Correct 8 ms 14380 KB Output is correct
3 Correct 10 ms 14304 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 8 ms 14420 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 7 ms 14420 KB Output is correct
9 Correct 7 ms 14420 KB Output is correct
10 Correct 7 ms 14436 KB Output is correct
11 Correct 8 ms 14608 KB Output is correct
12 Correct 8 ms 14420 KB Output is correct
13 Correct 8 ms 14420 KB Output is correct
14 Correct 10 ms 14548 KB Output is correct
15 Correct 8 ms 14560 KB Output is correct
16 Correct 61 ms 22328 KB Output is correct
17 Correct 58 ms 22324 KB Output is correct
18 Correct 60 ms 22260 KB Output is correct
19 Correct 53 ms 22088 KB Output is correct
20 Correct 55 ms 22084 KB Output is correct

Subtask #3
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Correct 8 ms 14380 KB Output is correct
3 Correct 10 ms 14304 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 8 ms 14420 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 7 ms 14420 KB Output is correct
9 Correct 7 ms 14420 KB Output is correct
10 Correct 7 ms 14436 KB Output is correct
11 Correct 8 ms 14608 KB Output is correct
12 Correct 8 ms 14420 KB Output is correct
13 Correct 8 ms 14420 KB Output is correct
14 Correct 10 ms 14548 KB Output is correct
15 Correct 8 ms 14560 KB Output is correct
16 Correct 61 ms 22328 KB Output is correct
17 Correct 58 ms 22324 KB Output is correct
18 Correct 60 ms 22260 KB Output is correct
19 Correct 53 ms 22088 KB Output is correct
20 Correct 55 ms 22084 KB Output is correct
21 Correct 149 ms 31800 KB Output is correct
22 Correct 8 ms 14420 KB Output is correct
23 Correct 169 ms 31892 KB Output is correct
24 Correct 147 ms 31752 KB Output is correct
25 Correct 163 ms 31828 KB Output is correct
26 Correct 185 ms 35280 KB Output is correct
27 Correct 156 ms 35240 KB Output is correct
28 Correct 173 ms 35264 KB Output is correct
29 Correct 198 ms 35228 KB Output is correct
30 Correct 209 ms 39240 KB Output is correct