Submission #341151

#	Time	Username	Problem	Language	Result	Execution time	Memory
341151		KWang31	Plus Minus (BOI17_plusminus)	Java	100 / 100	855 ms	50224 KiB

plusminus

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 / 12
• Subtask 2: 42 / 42
• Subtask 3: 46 / 46