Submission #3375500
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 if(now>=0){ int[] bin = {0, 1}; int cnt = 0; Queue<Integer> queue = new ArrayDeque<Integer>(); queue.add(now); while(queue.size()!=0){ 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){ break; } else{ queue.add(Search(literal, litvar, var[cnt])); } } } if(cnt>2046)ans = "TOO LARGE"; else{ int sum = -1; for(int i=0; i<=10; i++){ sum = 2*sum + 2; if(cnt<=sum){ ans = String.valueOf(i); break; } } } } else{ ans = "TOO LARGE"; } 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 | 2646 Byte |
Status | WA |
Exec Time | 2086 ms |
Memory | 225152 KB |
Judge Result
Set Name | All | ||||||
---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 200 | ||||||
Status |
|
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 | 96 ms | 19412 KB |
00-sample-10 | AC | 102 ms | 21972 KB |
00-sample-20 | AC | 116 ms | 22472 KB |
10-sat-00 | AC | 269 ms | 44028 KB |
10-sat-01 | AC | 220 ms | 41108 KB |
10-sat-02 | AC | 495 ms | 67204 KB |
10-sat-03 | WA | 317 ms | 43124 KB |
10-sat-04 | WA | 1548 ms | 131080 KB |
10-sat-05 | AC | 427 ms | 60776 KB |
10-sat-06 | TLE | 2086 ms | 218308 KB |
10-sat-07 | WA | 1478 ms | 137256 KB |
10-sat-08 | WA | 1257 ms | 219200 KB |
10-sat-09 | WA | 600 ms | 91516 KB |
10-sat-10 | WA | 1043 ms | 215884 KB |
10-sat-11 | WA | 702 ms | 110260 KB |
10-sat-12 | WA | 989 ms | 219004 KB |
10-sat-13 | WA | 1005 ms | 146192 KB |
10-sat-14 | WA | 889 ms | 224300 KB |
10-sat-15 | WA | 429 ms | 83288 KB |
10-sat-16 | WA | 882 ms | 223980 KB |
10-sat-17 | WA | 309 ms | 76604 KB |
10-sat-18 | WA | 800 ms | 224696 KB |
10-sat-19 | WA | 799 ms | 112220 KB |
10-sat-20 | WA | 797 ms | 222108 KB |
10-sat-21 | WA | 338 ms | 66996 KB |
10-sat-22 | AC | 684 ms | 225152 KB |
10-sat-23 | AC | 442 ms | 76616 KB |
10-sat-24 | AC | 673 ms | 217452 KB |
10-sat-25 | AC | 524 ms | 108864 KB |
10-sat-26 | AC | 719 ms | 221392 KB |
10-sat-27 | AC | 473 ms | 105548 KB |
10-sat-28 | AC | 679 ms | 217684 KB |
10-sat-29 | AC | 437 ms | 74376 KB |
10-sat-30 | AC | 725 ms | 216228 KB |
10-sat-31 | AC | 404 ms | 64832 KB |
10-sat-32 | AC | 697 ms | 220952 KB |
10-sat-33 | AC | 455 ms | 91784 KB |
10-sat-34 | AC | 678 ms | 222492 KB |
10-sat-35 | AC | 305 ms | 74684 KB |
10-sat-36 | AC | 671 ms | 217904 KB |
10-sat-37 | AC | 278 ms | 73796 KB |
10-sat-38 | AC | 704 ms | 222092 KB |
10-sat-39 | AC | 323 ms | 57480 KB |
20-unsat-00 | AC | 698 ms | 221048 KB |
20-unsat-01 | AC | 490 ms | 102800 KB |
20-unsat-02 | AC | 677 ms | 222152 KB |
20-unsat-03 | AC | 316 ms | 104468 KB |
20-unsat-04 | AC | 733 ms | 216884 KB |
20-unsat-05 | AC | 310 ms | 70580 KB |
20-unsat-06 | AC | 689 ms | 222824 KB |
20-unsat-07 | AC | 530 ms | 112220 KB |
20-unsat-08 | AC | 724 ms | 220100 KB |
20-unsat-09 | AC | 517 ms | 110596 KB |