oj.uz

Submission #341151

# Submission time Handle Problem Language Result Execution time Memory
341151 2020-12-29T04:18:22 Z KWang31 Plus Minus (BOI17_plusminus) Java 11
100 / 100
 855 ms 50224 KB 
import java.io.*; import java.util.*;
public class plusminus{
  static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        
    } 
    
    static int MOD=1000000007;
    static int[] rk, p,siz;
    static HashMap<Integer, Integer> labelB, labelC;
    public static void main(String[] args){
        FastReader br=new FastReader();
        int N=br.nextInt(); int M=br.nextInt(); int K=br.nextInt();
        int[][] cond=new int[K][3];
        for (int i = 0; i < K; i++) {
            if(br.next().charAt(0)=='+'){
                cond[i][2]++;
            }else{
                cond[i][2]--;
            }
            cond[i][0]=br.nextInt()-1; cond[i][1]=br.nextInt()-1; 
            
            
        }
        //a_ij=(-1)^i b_i + (-1)^j c_j - cond[i][2]
        //Case 1: a00=-1
        
        long cur1; long cur2; long ans=0;
        int i,j,k;
        boolean checkerboard;
        for (int X = -1; X <=1; X+=2) {//X=a00
            cur1=1; cur2=1; checkerboard=true;
            labelB=new HashMap<>(); labelC=new HashMap<>();
            //b is ai0, c is a0i
            labelB.put(0,X); labelC.put(0,X);
            for (int n = 0; n < K; n++) {//Case 1: c_j=X(-1)^j 
                
                i=cond[n][0]; j=cond[n][1]; k=cond[n][2];
                if((i+j)%2==0 ^ k==X)checkerboard=false;
                k*=(1-2*(j&1));
                
                    if(labelB.containsKey(i)){
                        if(labelB.get(i)!=k){
                            cur1=0; break;
                        }
                    }else{
                        labelB.put(i,k);
                    }
                
                
           }
            if(cur1==1){
                cur1=pow(N-labelB.size());
           }
            for (int n = 0; n < K; n++) {//Case 2
                
                i=cond[n][0]; j=cond[n][1]; k=cond[n][2]*(1-2*(i&1));
                
                    if(labelC.containsKey(j)){
                        if(labelC.get(j)!=k){
                            cur2=0; break;
                        }
                    }else{
                        labelC.put(j, k);
                    }
                
                
                
           }
            if(cur2==1){
                    
                    cur2=pow(M-labelC.size());
           }
           
           ans+=cur1; ans%=MOD; ans+=cur2; ans%=MOD;
           //System.out.println(cur1+" "+cur2+" "+checkerboard);
           if(cur1>0 && cur2>0 && checkerboard){//-1 only if checkerboard
               ans+=(MOD-1); ans%=MOD;
           }
           //System.out.println(X);
            //System.out.println(cur1+" "+cur2);
           //System.out.println(labelB);
           //System.out.println(labelC);
        }
        System.out.println((ans+MOD)%MOD);
    }
    public static long pow(int x){
        if(x==0)return 1; if(x==1)return 2;
        long y=pow(x/2);
        y*=y; y%=MOD; y*=pow(x&1); return y%MOD;
    }
    
    
}
//Debugging:
//Are you sure your algorithm is correct?
//Bounds: long
//Special cases: n=0,1?
//Make sure you remove your debugging code before you submit!

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 8556 KB Output is correct
2 Correct 71 ms 8556 KB Output is correct
3 Correct 71 ms 8448 KB Output is correct
4 Correct 73 ms 8428 KB Output is correct
5 Correct 72 ms 8556 KB Output is correct
6 Correct 74 ms 8556 KB Output is correct
7 Correct 71 ms 8556 KB Output is correct
8 Correct 71 ms 8556 KB Output is correct
9 Correct 72 ms 8556 KB Output is correct
10 Correct 71 ms 8556 KB Output is correct

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 8556 KB Output is correct
2 Correct 71 ms 8556 KB Output is correct
3 Correct 71 ms 8448 KB Output is correct
4 Correct 73 ms 8428 KB Output is correct
5 Correct 72 ms 8556 KB Output is correct
6 Correct 74 ms 8556 KB Output is correct
7 Correct 71 ms 8556 KB Output is correct
8 Correct 71 ms 8556 KB Output is correct
9 Correct 72 ms 8556 KB Output is correct
10 Correct 71 ms 8556 KB Output is correct
11 Correct 115 ms 8832 KB Output is correct
12 Correct 74 ms 8432 KB Output is correct
13 Correct 71 ms 8556 KB Output is correct
14 Correct 110 ms 8808 KB Output is correct
15 Correct 110 ms 8812 KB Output is correct
16 Correct 317 ms 18128 KB Output is correct
17 Correct 318 ms 18100 KB Output is correct
18 Correct 317 ms 18256 KB Output is correct
19 Correct 545 ms 21420 KB Output is correct
20 Correct 484 ms 20760 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 8556 KB Output is correct
2 Correct 71 ms 8556 KB Output is correct
3 Correct 71 ms 8448 KB Output is correct
4 Correct 73 ms 8428 KB Output is correct
5 Correct 72 ms 8556 KB Output is correct
6 Correct 74 ms 8556 KB Output is correct
7 Correct 71 ms 8556 KB Output is correct
8 Correct 71 ms 8556 KB Output is correct
9 Correct 72 ms 8556 KB Output is correct
10 Correct 71 ms 8556 KB Output is correct
11 Correct 115 ms 8832 KB Output is correct
12 Correct 74 ms 8432 KB Output is correct
13 Correct 71 ms 8556 KB Output is correct
14 Correct 110 ms 8808 KB Output is correct
15 Correct 110 ms 8812 KB Output is correct
16 Correct 317 ms 18128 KB Output is correct
17 Correct 318 ms 18100 KB Output is correct
18 Correct 317 ms 18256 KB Output is correct
19 Correct 545 ms 21420 KB Output is correct
20 Correct 484 ms 20760 KB Output is correct
21 Correct 726 ms 33500 KB Output is correct
22 Correct 73 ms 8684 KB Output is correct
23 Correct 329 ms 18132 KB Output is correct
24 Correct 331 ms 18196 KB Output is correct
25 Correct 337 ms 18148 KB Output is correct
26 Correct 599 ms 33628 KB Output is correct
27 Correct 620 ms 33344 KB Output is correct
28 Correct 562 ms 29672 KB Output is correct
29 Correct 762 ms 34752 KB Output is correct
30 Correct 855 ms 50224 KB Output is correct