oj.uz

Submission #124805

# Submission time Handle Problem Language Result Execution time Memory
124805 2019-07-04T02:22:15 Z model_code Plus Minus (BOI17_plusminus) Python 3
100 / 100
 359 ms 32892 KB 
#!/usr/bin/env python3
import sys
MOD = int(1e9) + 7 

def plusminus():
    n, m, k = map(int, sys.stdin.readline().split())
    row, col = {}, {}
    forced = []
    for i in range(k):
        line = sys.stdin.readline().split()
        sign, x, y = 1 if line[0] == "+" else -1, int(line[1])-1, int(line[2])-1
        forced.append((sign, x, y))
        
    # Two cases: either first row determine all rows, or first column
    # determine all columns; in case of both, there are two cases.
    
    # Case 1: how many ways if first row determines?
    rowscount = 1
    for sign, x, y in forced:
        rowforce = sign if y % 2 == 0 else -sign
        if x in row and row[x] == -rowforce:
            rowscount = 0
            break
        else:
            row[x] = rowforce
    
    freerows = n - len(row)
    rowscount *= pow(2, freerows, MOD)
    
    # Case 2: how many ways if first col determines?
    colscount = 1
    for sign, x, y in forced:
        colforce = sign if x % 2 == 0 else -sign
        if y in col and col[y] == -colforce:
            colscount = 0
            break
        else:
            col[y] = colforce
            
    freecols = m - len(col)
    colscount *= pow(2, freecols, MOD)
            
    # Case 3: how many ways if both rows and cols are determining?
    bothcount = 0
    if k == 0:
        bothcount = 2
    else:
        alleven = True
        allodd = True
        for sign, x, y in forced:
            sgn = max(0, sign)
            if (sgn + x + y) % 2 == 1:
                alleven = False
            else:
                allodd = False
        if alleven or allodd:
            bothcount = 1
        
    return (rowscount + colscount - bothcount) % MOD
        
    
print(plusminus())

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3428 KB Output is correct
2 Correct 24 ms 3428 KB Output is correct
3 Correct 25 ms 3428 KB Output is correct
4 Correct 25 ms 3428 KB Output is correct
5 Correct 24 ms 3428 KB Output is correct
6 Correct 25 ms 3428 KB Output is correct
7 Correct 25 ms 3428 KB Output is correct
8 Correct 26 ms 3428 KB Output is correct
9 Correct 25 ms 3428 KB Output is correct
10 Correct 27 ms 3400 KB Output is correct

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3428 KB Output is correct
2 Correct 24 ms 3428 KB Output is correct
3 Correct 25 ms 3428 KB Output is correct
4 Correct 25 ms 3428 KB Output is correct
5 Correct 24 ms 3428 KB Output is correct
6 Correct 25 ms 3428 KB Output is correct
7 Correct 25 ms 3428 KB Output is correct
8 Correct 26 ms 3428 KB Output is correct
9 Correct 25 ms 3428 KB Output is correct
10 Correct 27 ms 3400 KB Output is correct
11 Correct 28 ms 3428 KB Output is correct
12 Correct 25 ms 3428 KB Output is correct
13 Correct 26 ms 3420 KB Output is correct
14 Correct 28 ms 3428 KB Output is correct
15 Correct 27 ms 3428 KB Output is correct
16 Correct 260 ms 16144 KB Output is correct
17 Correct 260 ms 16020 KB Output is correct
18 Correct 261 ms 16144 KB Output is correct
19 Correct 337 ms 16040 KB Output is correct
20 Correct 338 ms 15988 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3428 KB Output is correct
2 Correct 24 ms 3428 KB Output is correct
3 Correct 25 ms 3428 KB Output is correct
4 Correct 25 ms 3428 KB Output is correct
5 Correct 24 ms 3428 KB Output is correct
6 Correct 25 ms 3428 KB Output is correct
7 Correct 25 ms 3428 KB Output is correct
8 Correct 26 ms 3428 KB Output is correct
9 Correct 25 ms 3428 KB Output is correct
10 Correct 27 ms 3400 KB Output is correct
11 Correct 28 ms 3428 KB Output is correct
12 Correct 25 ms 3428 KB Output is correct
13 Correct 26 ms 3420 KB Output is correct
14 Correct 28 ms 3428 KB Output is correct
15 Correct 27 ms 3428 KB Output is correct
16 Correct 260 ms 16144 KB Output is correct
17 Correct 260 ms 16020 KB Output is correct
18 Correct 261 ms 16144 KB Output is correct
19 Correct 337 ms 16040 KB Output is correct
20 Correct 338 ms 15988 KB Output is correct
21 Correct 355 ms 24964 KB Output is correct
22 Correct 28 ms 3448 KB Output is correct
23 Correct 265 ms 17600 KB Output is correct
24 Correct 264 ms 17540 KB Output is correct
25 Correct 262 ms 17548 KB Output is correct
26 Correct 262 ms 20440 KB Output is correct
27 Correct 261 ms 20260 KB Output is correct
28 Correct 279 ms 22812 KB Output is correct
29 Correct 294 ms 22784 KB Output is correct
30 Correct 359 ms 32892 KB Output is correct