oj.uz

Submission #338212

# Submission time Handle Problem Language Result Execution time Memory
338212 2020-12-22T17:52:16 Z KWang31 "The Lyuboyn" code (IZhO19_lyuboyn) Java 11
100 / 100
 501 ms 43428 KB 
import java.util.*; import java.io.*;
public class lyuboyn {

    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 void main(String[] args) {
        FastReader br=new FastReader();
        int N=br.nextInt(); int K=br.nextInt(); int T=br.nextInt();
        if((K&1)==0){
            System.out.println("-1");return;
        }
        int[] cur=new int[1<<(K+1)];//Start with (K,K+1)
        for (int i = 1; i < 1<<(K+1); i++) {
            int j=0; while((i&(1<<j))==0){j++;}
            cur[i]=((1<<(K+1))-1-cur[i-1])^(1<<j);
            
        }
        //System.out.println(Arrays.toString(cur));
        for(int B=K+2; B<=N; B++){
            int[] nxt=new int[1<<B];
            nxt[1]=(1<<(B-1))+(1<<(K-1))-1;
            for(int j=2; j<=(1<<(B-1)); j++){
                nxt[j]=nxt[1]^cur[j-1];
            }
            for(int j=(1<<(B-1))+1; j<(1<<B); j++){
                nxt[j]=cur[(1<<B)-j];
            }
            cur=new int[1<<B]; for(int i=0;i<(1<<B); i++) {cur[i]=nxt[i];}
        }
        //System.out.println(Arrays.toString(cur));
        int st=Integer.parseInt(br.next(),2);
        if(T==1){
            System.out.println(1<<N);
            StringBuilder sb=new StringBuilder();
            for (int i = 0; i < (1<<N); i++) {
                sb.append(Integer.toString((1<<N)+(st^cur[i]),2).substring(1)+"\n");
            }
            System.out.println(sb.toString());
        }else{
            /*
            if(K==1 && N==2){
                System.out.println(-1);return;
            }*/
            int sta=0;
            
            for (int i = 0; i < (1<<N); i++) {
                if(Integer.bitCount(cur[i]^cur[(i+3)%(1<<N)])==K){
                    //System.out.println(i); break;
                    cur[i]+=cur[(i+2)%(1<<N)]; cur[(i+2)%(1<<N)]=cur[i]-cur[(i+2)%(1<<N)]; cur[i]-=cur[(i+2)%(1<<N)]; 
                    sta=i; break;
                }
            }
            System.out.println(1<<N);
            StringBuilder sb=new StringBuilder();
            for (int i = 0; i < (1<<N); i++) {
                sb.append(Integer.toString((1<<N)+(st^cur[(sta+i)%(1<<N)]^cur[sta]),2).substring(1)+"\n");
            }
            System.out.println(sb.toString());
        }
    }
    
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 9580 KB Ok

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 9524 KB Ok

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 8668 KB Ok
2 Correct 85 ms 8440 KB Ok
3 Correct 72 ms 8556 KB Ok
4 Correct 75 ms 8556 KB Ok
5 Correct 71 ms 8556 KB Ok
6 Correct 73 ms 8556 KB Ok
7 Correct 74 ms 8556 KB Ok
8 Correct 71 ms 8684 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 501 ms 43076 KB Ok
2 Correct 408 ms 26136 KB Ok
3 Correct 155 ms 11508 KB Ok
4 Correct 114 ms 9452 KB Ok
5 Correct 113 ms 9580 KB Ok

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 9580 KB Ok
2 Correct 301 ms 15632 KB Ok
3 Correct 415 ms 26024 KB Ok
4 Correct 384 ms 19240 KB Ok
5 Correct 121 ms 9708 KB Ok
6 Correct 191 ms 11800 KB Ok
7 Correct 366 ms 17084 KB Ok
8 Correct 117 ms 9836 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 43176 KB Ok
2 Correct 469 ms 43116 KB Ok
3 Correct 478 ms 43428 KB Ok
4 Correct 409 ms 26060 KB Ok
5 Correct 409 ms 26008 KB Ok
6 Correct 380 ms 19480 KB Ok
7 Correct 381 ms 19084 KB Ok
8 Correct 365 ms 17176 KB Ok
9 Correct 368 ms 17192 KB Ok
10 Correct 360 ms 16428 KB Ok
11 Correct 158 ms 11416 KB Ok
12 Correct 154 ms 11544 KB Ok
13 Correct 119 ms 9708 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 501 ms 43076 KB Ok
2 Correct 408 ms 26136 KB Ok
3 Correct 155 ms 11508 KB Ok
4 Correct 114 ms 9452 KB Ok
5 Correct 113 ms 9580 KB Ok
6 Correct 115 ms 9580 KB Ok
7 Correct 301 ms 15632 KB Ok
8 Correct 415 ms 26024 KB Ok
9 Correct 384 ms 19240 KB Ok
10 Correct 121 ms 9708 KB Ok
11 Correct 191 ms 11800 KB Ok
12 Correct 366 ms 17084 KB Ok
13 Correct 117 ms 9836 KB Ok
14 Correct 474 ms 43176 KB Ok
15 Correct 469 ms 43116 KB Ok
16 Correct 478 ms 43428 KB Ok
17 Correct 409 ms 26060 KB Ok
18 Correct 409 ms 26008 KB Ok
19 Correct 380 ms 19480 KB Ok
20 Correct 381 ms 19084 KB Ok
21 Correct 365 ms 17176 KB Ok
22 Correct 368 ms 17192 KB Ok
23 Correct 360 ms 16428 KB Ok
24 Correct 158 ms 11416 KB Ok
25 Correct 154 ms 11544 KB Ok
26 Correct 119 ms 9708 KB Ok
27 Correct 426 ms 39176 KB Ok
28 Correct 421 ms 25556 KB Ok
29 Correct 453 ms 42836 KB Ok
30 Correct 362 ms 16188 KB Ok
31 Correct 152 ms 11304 KB Ok
32 Correct 251 ms 13400 KB Ok
33 Correct 338 ms 15136 KB Ok
34 Correct 117 ms 9580 KB Ok
35 Correct 110 ms 9580 KB Ok
36 Correct 120 ms 9708 KB Ok
37 Correct 110 ms 9580 KB Ok
38 Correct 382 ms 23776 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 23584 KB Ok
2 Correct 431 ms 38968 KB Ok
3 Correct 453 ms 42836 KB Ok
4 Correct 358 ms 16296 KB Ok
5 Correct 117 ms 9708 KB Ok
6 Correct 338 ms 15136 KB Ok
7 Correct 468 ms 43200 KB Ok
8 Correct 154 ms 11432 KB Ok
9 Correct 113 ms 9580 KB Ok
10 Correct 154 ms 11304 KB Ok
11 Correct 338 ms 17168 KB Ok
12 Correct 418 ms 25444 KB Ok