Submission #3377240


Source Code Expand

import java.util.*;
public class Main{
	static int Search(String[][] literal, int[][] litvar, String var){
		int index = -1;
		for(int i=0; i<literal[0].length; i++){
			String lit1 = literal[0][i];
			String lit2 = literal[1][i];
			char var1 = var.charAt(litvar[0][i]);
			char var2 = var.charAt(litvar[1][i]);
			if((lit1.charAt(0)!='~'&&lit2.charAt(0)!='~'&&var1=='F'&&var2=='F')||(lit1.charAt(0)=='~'&&lit2.charAt(0)!='~'&&var1=='T'&&var2=='F')||(lit1.charAt(0)!='~'&&lit2.charAt(0)=='~'&&var1=='F'&&var2=='T')||(lit1.charAt(0)=='~'&&lit2.charAt(0)=='~'&&var1=='T'&&var2=='T')){
				index = i;
				break;
			}
		}
		return index;
	}
 
	static String Changevar(String var, int litvar){
		StringBuilder sb = new StringBuilder(var);
		if(var.charAt(litvar)=='T'){
			sb.setCharAt(litvar, 'F');
		}
		else{
			sb.setCharAt(litvar, 'T');
		}
		return sb.toString();
	}
 
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		String cnf = sc.next();
		String a = sc.next();
		String[] clause = new String[m];
		String[][] literal = new String[2][m];
		int[][] litvar = new int[2][m];
		Arrays.fill(clause, "");
		int j = 1;
		for(int i=0; i<m; i++){
			while(!cnf.substring(j, j+1).equals(")")){
				clause[i] += cnf.substring(j, j+1);
				j++;
			}
			j += 3;
		}
		for(int i=0; i<m; i++){
			String[] spl = clause[i].split("v", 0);
			for(int k=0; k<=1; k++){
				literal[k][i] = spl[k];
				if(literal[k][i].charAt(0)=='~'){
					litvar[k][i] = Integer.parseInt(literal[k][i].substring(1)) - 1;
				}
				else{
					litvar[k][i] = Integer.parseInt(literal[k][i]) - 1;
				}
			}
		}
 
		String ans = "";
		String[] var = new String[2050];
		var[0] = a;
		int now = Search(literal, litvar, var[0]);
		if(now<0){
			ans = "0";
		}
		else{
			int cnt = 0;
			Queue<Integer> queue = new ArrayDeque<Integer>();
			queue.add(now);
			while(queue.size()!=0){
				boolean flag = false;
				now = queue.poll();
				for(int i=0; i<=1; i++){
					cnt++;
					if(cnt>2046){
						break;
					}
					var[cnt] = Changevar(var[(cnt+1)/2-1], litvar[i][now]);
					if(Search(literal, litvar, var[cnt])<0){
						flag = true;
						break;
					}
					else{
						queue.add(Search(literal, litvar, var[cnt]));
					}
				}
				if(cnt>2046){
					ans = "TOO LARGE";
					break;
				}
				if(flag==true){
					int sum = -1;
					for(int i=0; i<=10; i++){
						sum = 2*sum + 2;
						if(cnt<=sum){
							ans = String.valueOf(i);
							break;
						}
					}
				}
			}
		}
		System.out.println(ans);
	}
}

Submission Info

Submission Time
Task E - 2-SAT
User Ricky_pon
Language Java8 (OpenJDK 1.8.0)
Score 0
Code Size 2667 Byte
Status WA
Exec Time 1870 ms
Memory 227660 KB

Judge Result

Set Name All
Score / Max Score 0 / 200
Status
AC × 35
WA × 18
Set Name Test Cases
All 00-sample-00, 00-sample-10, 00-sample-20, 10-sat-00, 10-sat-01, 10-sat-02, 10-sat-03, 10-sat-04, 10-sat-05, 10-sat-06, 10-sat-07, 10-sat-08, 10-sat-09, 10-sat-10, 10-sat-11, 10-sat-12, 10-sat-13, 10-sat-14, 10-sat-15, 10-sat-16, 10-sat-17, 10-sat-18, 10-sat-19, 10-sat-20, 10-sat-21, 10-sat-22, 10-sat-23, 10-sat-24, 10-sat-25, 10-sat-26, 10-sat-27, 10-sat-28, 10-sat-29, 10-sat-30, 10-sat-31, 10-sat-32, 10-sat-33, 10-sat-34, 10-sat-35, 10-sat-36, 10-sat-37, 10-sat-38, 10-sat-39, 20-unsat-00, 20-unsat-01, 20-unsat-02, 20-unsat-03, 20-unsat-04, 20-unsat-05, 20-unsat-06, 20-unsat-07, 20-unsat-08, 20-unsat-09
Case Name Status Exec Time Memory
00-sample-00 AC 92 ms 20692 KB
00-sample-10 AC 99 ms 22740 KB
00-sample-20 AC 113 ms 23508 KB
10-sat-00 AC 249 ms 42452 KB
10-sat-01 AC 216 ms 43344 KB
10-sat-02 AC 411 ms 64996 KB
10-sat-03 WA 322 ms 45628 KB
10-sat-04 WA 1526 ms 132500 KB
10-sat-05 AC 385 ms 59764 KB
10-sat-06 WA 1870 ms 221176 KB
10-sat-07 WA 1510 ms 140512 KB
10-sat-08 WA 1111 ms 214052 KB
10-sat-09 WA 696 ms 94984 KB
10-sat-10 WA 956 ms 217980 KB
10-sat-11 WA 717 ms 107636 KB
10-sat-12 WA 898 ms 218248 KB
10-sat-13 WA 909 ms 149212 KB
10-sat-14 WA 906 ms 224480 KB
10-sat-15 WA 413 ms 82296 KB
10-sat-16 WA 886 ms 227660 KB
10-sat-17 WA 269 ms 76052 KB
10-sat-18 WA 764 ms 225600 KB
10-sat-19 WA 541 ms 113684 KB
10-sat-20 WA 688 ms 222636 KB
10-sat-21 WA 358 ms 69236 KB
10-sat-22 AC 658 ms 220080 KB
10-sat-23 AC 446 ms 81276 KB
10-sat-24 AC 636 ms 223380 KB
10-sat-25 AC 545 ms 113844 KB
10-sat-26 AC 659 ms 223052 KB
10-sat-27 AC 455 ms 108836 KB
10-sat-28 AC 706 ms 219072 KB
10-sat-29 AC 396 ms 76156 KB
10-sat-30 AC 645 ms 220044 KB
10-sat-31 AC 404 ms 61032 KB
10-sat-32 AC 664 ms 220024 KB
10-sat-33 AC 438 ms 91684 KB
10-sat-34 AC 656 ms 224796 KB
10-sat-35 AC 279 ms 75704 KB
10-sat-36 AC 648 ms 218604 KB
10-sat-37 AC 289 ms 74164 KB
10-sat-38 AC 656 ms 221416 KB
10-sat-39 AC 318 ms 57348 KB
20-unsat-00 AC 670 ms 217872 KB
20-unsat-01 AC 530 ms 107020 KB
20-unsat-02 AC 658 ms 218448 KB
20-unsat-03 AC 316 ms 106152 KB
20-unsat-04 AC 528 ms 151080 KB
20-unsat-05 AC 317 ms 74312 KB
20-unsat-06 AC 692 ms 219348 KB
20-unsat-07 AC 532 ms 111772 KB
20-unsat-08 AC 685 ms 218176 KB
20-unsat-09 AC 488 ms 112204 KB