oj.uz

Submission #338211

# Submission time Handle Problem Language Result Execution time Memory
338211 2020-12-22T17:48:37 Z KWang31 "The Lyuboyn" code (IZhO19_lyuboyn) Java 11
69 / 100
 489 ms 43544 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 110 ms 9600 KB Ok

Subtask #2
5.0 / 5.0

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

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 8556 KB Ok
2 Correct 71 ms 8556 KB Ok
3 Correct 72 ms 8540 KB Ok
4 Correct 72 ms 8468 KB Ok
5 Correct 74 ms 8512 KB Ok
6 Correct 71 ms 8540 KB Ok
7 Correct 72 ms 8556 KB Ok
8 Correct 76 ms 8540 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 43328 KB Ok
2 Correct 420 ms 26316 KB Ok
3 Correct 155 ms 11432 KB Ok
4 Correct 113 ms 9580 KB Ok
5 Correct 116 ms 9704 KB Ok

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 9552 KB Ok
2 Correct 313 ms 15624 KB Ok
3 Correct 420 ms 26248 KB Ok
4 Correct 387 ms 19584 KB Ok
5 Correct 121 ms 9708 KB Ok
6 Correct 191 ms 11736 KB Ok
7 Correct 370 ms 17244 KB Ok
8 Correct 114 ms 9820 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 43536 KB Ok
2 Correct 482 ms 43544 KB Ok
3 Correct 489 ms 43408 KB Ok
4 Correct 413 ms 26252 KB Ok
5 Correct 417 ms 26252 KB Ok
6 Correct 382 ms 19468 KB Ok
7 Correct 380 ms 19228 KB Ok
8 Correct 372 ms 17292 KB Ok
9 Correct 380 ms 17420 KB Ok
10 Correct 371 ms 16308 KB Ok
11 Correct 156 ms 11556 KB Ok
12 Correct 153 ms 11372 KB Ok
13 Correct 115 ms 9640 KB Ok

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 43328 KB Ok
2 Correct 420 ms 26316 KB Ok
3 Correct 155 ms 11432 KB Ok
4 Correct 113 ms 9580 KB Ok
5 Correct 116 ms 9704 KB Ok
6 Correct 114 ms 9552 KB Ok
7 Correct 313 ms 15624 KB Ok
8 Correct 420 ms 26248 KB Ok
9 Correct 387 ms 19584 KB Ok
10 Correct 121 ms 9708 KB Ok
11 Correct 191 ms 11736 KB Ok
12 Correct 370 ms 17244 KB Ok
13 Correct 114 ms 9820 KB Ok
14 Correct 487 ms 43536 KB Ok
15 Correct 482 ms 43544 KB Ok
16 Correct 489 ms 43408 KB Ok
17 Correct 413 ms 26252 KB Ok
18 Correct 417 ms 26252 KB Ok
19 Correct 382 ms 19468 KB Ok
20 Correct 380 ms 19228 KB Ok
21 Correct 372 ms 17292 KB Ok
22 Correct 380 ms 17420 KB Ok
23 Correct 371 ms 16308 KB Ok
24 Correct 156 ms 11556 KB Ok
25 Correct 153 ms 11372 KB Ok
26 Correct 115 ms 9640 KB Ok
27 Correct 427 ms 39176 KB Ok
28 Correct 435 ms 25556 KB Ok
29 Correct 464 ms 42800 KB Ok
30 Correct 363 ms 16396 KB Ok
31 Correct 157 ms 11304 KB Ok
32 Correct 248 ms 13144 KB Ok
33 Correct 339 ms 15088 KB Ok
34 Correct 119 ms 9708 KB Ok
35 Correct 111 ms 9436 KB Ok
36 Correct 116 ms 9836 KB Ok
37 Incorrect 69 ms 8556 KB Output -1 while solution exists
38 Halted 0 ms 0 KB -

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 23348 KB Ok
2 Correct 442 ms 39016 KB Ok
3 Correct 478 ms 43084 KB Ok
4 Correct 360 ms 16524 KB Ok
5 Correct 118 ms 9680 KB Ok
6 Correct 337 ms 15088 KB Ok
7 Correct 487 ms 43408 KB Ok
8 Correct 162 ms 11432 KB Ok
9 Correct 125 ms 9552 KB Ok
10 Correct 155 ms 11432 KB Ok
11 Correct 330 ms 17052 KB Ok
12 Correct 437 ms 25608 KB Ok