답안 #337231

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
337231	2020-12-19T01:58:24 Z	KWang31	Snake Escaping (JOI18_snake_escaping)	Java 11	75 / 100	1546 ms	65536 KB

snake_escaping

import java.io.*; import java.util.*;
public class snake_escaping{
  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()); 
        } 
  
        
    } 
  
    public static class Pair implements Comparable<Pair>{
        int vtx; int val;
        public Pair(int a, int b){
            this.vtx=a; this.val=b;
        }
        public int compareTo(Pair other){
            if(this.val<other.val)return -1;
            if(this.val>other.val)return 1;
            if(this.vtx<other.vtx)return -1;
            return 1;
        }
    }
    static int MOD=998244353;
    
    public static void main(String[] args){
        FastReader br=new FastReader();
        int L=br.nextInt(); int Q=br.nextInt();
        final int[] S=new int[1<<L]; final int[] sup=new int[1<<L]; final int[] sub=new int[1<<L];
        final int[] btcnt=new int[1<<L];
        String s=br.next();
        for(int i=0; i<(1<<L); i++){
            S[i]=(int) s.charAt(i)-'0'; sup[i]=sub[i]=S[i];
            btcnt[i]=Integer.bitCount(i);
        }
        //SOS DP!!
        for(int b=0; b<L; b++){
            for(int m=0;m<(1<<L); m++){
                if(((m>>>b)&1) ==0){
                    sup[m]+=sup[m^(1<<b)];
                }else{
                    sub[m]+=sub[m^(1<<b)];
                }
            }
        }
        //System.out.println(Arrays.toString(sub));
        //System.out.println(Arrays.toString(sup));
        StringBuilder sb=new StringBuilder();
        //sb can have a lot of memory
        int A; int B; int C;
        int ca; int cb; int cc; long ans;
        for(int i=0;i<Q;i++){
            s=br.next(); A=0; B=0; C=0;
            ca=0; cb=0; cc=0; ans=0;
            for(int j=0;j<L;j++){
                if(s.charAt(j)=='0'){A|=(1<<(L-j-1)); ca++;}
                else if(s.charAt(j)=='1') {B|=(1<<(L-j-1)); cb++;}
                else {C|=(1<<(L-j-1)); cc++;}
            }
            //System.out.println(ca+" "+cb+" "+cc);
            if(ca<=cb && ca<=cc){
                for(int m=A; m!=0; m=(m-1)&A){
                    ans+=(1-2*((btcnt[m])&1))*sup[B|m];
                }
                ans+=sup[B];
            }else if(cb<=ca && cb<=cc){
                for(int m=B; m!=0; m=(m-1)&B){
                    
                    ans+=(1-2*((btcnt[m])&1))*sub[C|(B^m)];
                    
                }
                ans+=sub[C|B];
                
            }else{
                for(int m=C; m!=0; m=(m-1)&C){
                    
                    ans+=S[m|B];
                }
                //System.out.println(A+" "+B);
                ans+=S[B];
            }
            sb.append(ans).append("\n");
        }
        System.out.println(sb.toString());
    }
    
    
    
}
//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
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	120 ms	10256 KB	Output is correct
2	Correct	118 ms	10264 KB	Output is correct
3	Correct	126 ms	10536 KB	Output is correct
4	Correct	119 ms	10232 KB	Output is correct
5	Correct	124 ms	10320 KB	Output is correct
6	Correct	120 ms	10388 KB	Output is correct
7	Correct	142 ms	10388 KB	Output is correct
8	Correct	148 ms	10516 KB	Output is correct
9	Correct	119 ms	10372 KB	Output is correct
10	Correct	124 ms	10232 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	120 ms	10256 KB	Output is correct
2	Correct	118 ms	10264 KB	Output is correct
3	Correct	126 ms	10536 KB	Output is correct
4	Correct	119 ms	10232 KB	Output is correct
5	Correct	124 ms	10320 KB	Output is correct
6	Correct	120 ms	10388 KB	Output is correct
7	Correct	142 ms	10388 KB	Output is correct
8	Correct	148 ms	10516 KB	Output is correct
9	Correct	119 ms	10372 KB	Output is correct
10	Correct	124 ms	10232 KB	Output is correct
11	Correct	603 ms	37460 KB	Output is correct
12	Correct	619 ms	36676 KB	Output is correct
13	Correct	636 ms	35396 KB	Output is correct
14	Correct	640 ms	35424 KB	Output is correct
15	Correct	621 ms	37756 KB	Output is correct
16	Correct	641 ms	35620 KB	Output is correct
17	Correct	652 ms	35668 KB	Output is correct
18	Correct	559 ms	46524 KB	Output is correct
19	Correct	549 ms	31372 KB	Output is correct
20	Correct	606 ms	36868 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	120 ms	10256 KB	Output is correct
2	Correct	118 ms	10264 KB	Output is correct
3	Correct	126 ms	10536 KB	Output is correct
4	Correct	119 ms	10232 KB	Output is correct
5	Correct	124 ms	10320 KB	Output is correct
6	Correct	120 ms	10388 KB	Output is correct
7	Correct	142 ms	10388 KB	Output is correct
8	Correct	148 ms	10516 KB	Output is correct
9	Correct	119 ms	10372 KB	Output is correct
10	Correct	124 ms	10232 KB	Output is correct
11	Correct	603 ms	37460 KB	Output is correct
12	Correct	619 ms	36676 KB	Output is correct
13	Correct	636 ms	35396 KB	Output is correct
14	Correct	640 ms	35424 KB	Output is correct
15	Correct	621 ms	37756 KB	Output is correct
16	Correct	641 ms	35620 KB	Output is correct
17	Correct	652 ms	35668 KB	Output is correct
18	Correct	559 ms	46524 KB	Output is correct
19	Correct	549 ms	31372 KB	Output is correct
20	Correct	606 ms	36868 KB	Output is correct
21	Correct	682 ms	40932 KB	Output is correct
22	Correct	714 ms	43024 KB	Output is correct
23	Correct	741 ms	39056 KB	Output is correct
24	Correct	732 ms	38912 KB	Output is correct
25	Correct	741 ms	49776 KB	Output is correct
26	Correct	803 ms	39804 KB	Output is correct
27	Correct	764 ms	39852 KB	Output is correct
28	Correct	677 ms	51556 KB	Output is correct
29	Correct	665 ms	34796 KB	Output is correct
30	Correct	692 ms	42792 KB	Output is correct
31	Correct	757 ms	40732 KB	Output is correct
32	Correct	715 ms	40884 KB	Output is correct
33	Correct	682 ms	38792 KB	Output is correct
34	Correct	764 ms	38844 KB	Output is correct
35	Correct	754 ms	39824 KB	Output is correct
36	Correct	545 ms	34844 KB	Output is correct
37	Correct	661 ms	40672 KB	Output is correct
38	Correct	690 ms	34952 KB	Output is correct
39	Correct	727 ms	39140 KB	Output is correct
40	Correct	711 ms	38816 KB	Output is correct

Subtask #4
53.0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	120 ms	10256 KB	Output is correct
2	Correct	118 ms	10264 KB	Output is correct
3	Correct	126 ms	10536 KB	Output is correct
4	Correct	119 ms	10232 KB	Output is correct
5	Correct	124 ms	10320 KB	Output is correct
6	Correct	120 ms	10388 KB	Output is correct
7	Correct	142 ms	10388 KB	Output is correct
8	Correct	148 ms	10516 KB	Output is correct
9	Correct	119 ms	10372 KB	Output is correct
10	Correct	124 ms	10232 KB	Output is correct
11	Correct	490 ms	41604 KB	Output is correct
12	Correct	483 ms	41884 KB	Output is correct
13	Correct	528 ms	41712 KB	Output is correct
14	Correct	544 ms	41500 KB	Output is correct
15	Correct	497 ms	42492 KB	Output is correct
16	Correct	532 ms	41836 KB	Output is correct
17	Correct	519 ms	41780 KB	Output is correct
18	Correct	483 ms	42644 KB	Output is correct
19	Correct	466 ms	41048 KB	Output is correct
20	Correct	480 ms	41952 KB	Output is correct
21	Correct	523 ms	42008 KB	Output is correct
22	Correct	536 ms	41312 KB	Output is correct
23	Correct	487 ms	41592 KB	Output is correct
24	Correct	537 ms	41760 KB	Output is correct
25	Correct	515 ms	41528 KB	Output is correct
26	Correct	468 ms	41068 KB	Output is correct
27	Correct	478 ms	41824 KB	Output is correct
28	Correct	467 ms	41144 KB	Output is correct
29	Correct	527 ms	41672 KB	Output is correct
30	Correct	511 ms	41440 KB	Output is correct
31	Correct	483 ms	41564 KB	Output is correct
32	Correct	532 ms	41908 KB	Output is correct
33	Correct	530 ms	41528 KB	Output is correct
34	Correct	463 ms	41180 KB	Output is correct
35	Correct	507 ms	41760 KB	Output is correct
36	Correct	508 ms	41628 KB	Output is correct
37	Correct	515 ms	41656 KB	Output is correct
38	Correct	513 ms	41764 KB	Output is correct
39	Correct	509 ms	41784 KB	Output is correct
40	Correct	506 ms	41724 KB	Output is correct

Subtask #5
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	120 ms	10256 KB	Output is correct
2	Correct	118 ms	10264 KB	Output is correct
3	Correct	126 ms	10536 KB	Output is correct
4	Correct	119 ms	10232 KB	Output is correct
5	Correct	124 ms	10320 KB	Output is correct
6	Correct	120 ms	10388 KB	Output is correct
7	Correct	142 ms	10388 KB	Output is correct
8	Correct	148 ms	10516 KB	Output is correct
9	Correct	119 ms	10372 KB	Output is correct
10	Correct	124 ms	10232 KB	Output is correct
11	Correct	603 ms	37460 KB	Output is correct
12	Correct	619 ms	36676 KB	Output is correct
13	Correct	636 ms	35396 KB	Output is correct
14	Correct	640 ms	35424 KB	Output is correct
15	Correct	621 ms	37756 KB	Output is correct
16	Correct	641 ms	35620 KB	Output is correct
17	Correct	652 ms	35668 KB	Output is correct
18	Correct	559 ms	46524 KB	Output is correct
19	Correct	549 ms	31372 KB	Output is correct
20	Correct	606 ms	36868 KB	Output is correct
21	Correct	682 ms	40932 KB	Output is correct
22	Correct	714 ms	43024 KB	Output is correct
23	Correct	741 ms	39056 KB	Output is correct
24	Correct	732 ms	38912 KB	Output is correct
25	Correct	741 ms	49776 KB	Output is correct
26	Correct	803 ms	39804 KB	Output is correct
27	Correct	764 ms	39852 KB	Output is correct
28	Correct	677 ms	51556 KB	Output is correct
29	Correct	665 ms	34796 KB	Output is correct
30	Correct	692 ms	42792 KB	Output is correct
31	Correct	757 ms	40732 KB	Output is correct
32	Correct	715 ms	40884 KB	Output is correct
33	Correct	682 ms	38792 KB	Output is correct
34	Correct	764 ms	38844 KB	Output is correct
35	Correct	754 ms	39824 KB	Output is correct
36	Correct	545 ms	34844 KB	Output is correct
37	Correct	661 ms	40672 KB	Output is correct
38	Correct	690 ms	34952 KB	Output is correct
39	Correct	727 ms	39140 KB	Output is correct
40	Correct	711 ms	38816 KB	Output is correct
41	Correct	490 ms	41604 KB	Output is correct
42	Correct	483 ms	41884 KB	Output is correct
43	Correct	528 ms	41712 KB	Output is correct
44	Correct	544 ms	41500 KB	Output is correct
45	Correct	497 ms	42492 KB	Output is correct
46	Correct	532 ms	41836 KB	Output is correct
47	Correct	519 ms	41780 KB	Output is correct
48	Correct	483 ms	42644 KB	Output is correct
49	Correct	466 ms	41048 KB	Output is correct
50	Correct	480 ms	41952 KB	Output is correct
51	Correct	523 ms	42008 KB	Output is correct
52	Correct	536 ms	41312 KB	Output is correct
53	Correct	487 ms	41592 KB	Output is correct
54	Correct	537 ms	41760 KB	Output is correct
55	Correct	515 ms	41528 KB	Output is correct
56	Correct	468 ms	41068 KB	Output is correct
57	Correct	478 ms	41824 KB	Output is correct
58	Correct	467 ms	41144 KB	Output is correct
59	Correct	527 ms	41672 KB	Output is correct
60	Correct	511 ms	41440 KB	Output is correct
61	Correct	483 ms	41564 KB	Output is correct
62	Correct	532 ms	41908 KB	Output is correct
63	Correct	530 ms	41528 KB	Output is correct
64	Correct	463 ms	41180 KB	Output is correct
65	Correct	507 ms	41760 KB	Output is correct
66	Correct	508 ms	41628 KB	Output is correct
67	Correct	515 ms	41656 KB	Output is correct
68	Correct	513 ms	41764 KB	Output is correct
69	Correct	509 ms	41784 KB	Output is correct
70	Correct	506 ms	41724 KB	Output is correct
71	Correct	1000 ms	65536 KB	Output is correct
72	Correct	1012 ms	65536 KB	Output is correct
73	Correct	1289 ms	65536 KB	Output is correct
74	Correct	1546 ms	65536 KB	Output is correct
75	Runtime error	966 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
76	Halted	0 ms	0 KB	-

답안 #337231

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 10.0 / 10.0

Subtask #4 53.0 / 53.0

Subtask #5 0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
7.0 / 7.0

Subtask #3
10.0 / 10.0

Subtask #4
53.0 / 53.0

Subtask #5
0 / 25.0