oj.uz

Submission #476812

# Submission time Handle Problem Language Result Execution time Memory
476812 2021-09-28T14:57:43 Z KWang31 Sob (COCI19_sob) Java 11
110 / 110
 843 ms 84624 KB 
import java.io.*; import java.util.*;
public class sob{
  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;
    static int[] rk, p,siz;
    public static void main(String[] args){
        FastReader br=new FastReader();
        int N=br.nextInt(); int M=br.nextInt();
        int[][] ans=solve(N,M);
        StringBuilder sb=new StringBuilder();
        for(int i=0; i<N; i++) {
        	
        	
        	sb.append(ans[i][0]+" "+ans[i][1]+'\n');
        }
        //StringBuilder sb=new StringBuilder();
        System.out.println(sb.toString());
    }
    public static int[][] solve(int N, int M){
    	int[][] ans=new int[N][2];
    	//Base Case: N=1
    	if(N==1) {
    		
    		ans[0][0]=0; ans[0][1]=M;
    	}else {
    		if((N&1)==0 && (M&1)==0) {// Case 1: N even
    			int[][] cur=solve(N/2, M/2);
    			
    			for(int i=0; i<N/2; i++) {
    				for(int j=0; j<2; j++) {
    					ans[2*i+j][0]=cur[i][0]*2+j;
    					ans[2*i+j][1]=cur[i][1]*2+j;
    				}
    			}
    		}else if((N&1)==0 && (M&1)==1) {
    			int[][] cur=solve(N/2, (M+1)/2);
    			
    			for(int i=0; i<N/2; i++) {
    				for(int j=0; j<2; j++) {
    					ans[i][j]=cur[i][j]*2;
    				}
    			}
    			int[][] cur2=solve(N/2, (M-1)/2);
    			for(int i=0; i<N/2; i++) {
    				for(int j=0; j<2; j++) {
    					ans[i+N/2][j]=cur2[i][j]*2+1;
    				}
    			}
    		}else if((N&1)==1) {
    			if((M&1)==0) {
    				int[][] cur=solve((N+1)/2, M/2);
    				for(int i=0; i<(N+1)/2; i++){
    					for(int j=0; j<2; j++) {
    						ans[i][j]=cur[i][j]*2;
    					}
    				}
    				int[][] cur2=solve((N-1)/2, M/2);
    				for(int i=0; i<(N-1)/2; i++){
    					for(int j=0; j<2; j++) {
    						ans[i+(N+1)/2][j]=cur2[i][j]*2+1;
    					}
    				}
    			}else {
    				int[][] cur=solve((N+1)/2, (M-1)/2);
    				//I will pretend M is M-1 in this process
    				for(int i=0; i<(N+1)/2; i++) {
    					for(int j=0; j<2; j++) {
    						ans[i][j]=cur[i][j]*2;
    						if(j==1 && ans[i][j]==M-1) {
    							ans[i][j]=M;
    						}
    					}
    				}
    				int[][] cur2=solve((N-1)/2, (M+1)/2);
    				for(int i=0; i<(N-1)/2; i++) {
    					for(int j=0;j<2;j++) {
    						ans[i+(N+1)/2][j]=cur2[i][j]*2+1;
    					}
    				}
    			}
    		}
    		
    	}
    	return ans;
    }
    
}
//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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 10644 KB Output is correct
2 Correct 129 ms 10196 KB Output is correct
3 Correct 126 ms 10404 KB Output is correct
4 Correct 503 ms 47084 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 13212 KB Output is correct
2 Correct 137 ms 10424 KB Output is correct
3 Correct 127 ms 10328 KB Output is correct
4 Correct 138 ms 10380 KB Output is correct
5 Correct 142 ms 10412 KB Output is correct
6 Correct 472 ms 47096 KB Output is correct
7 Correct 442 ms 29488 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 10180 KB Output is correct
2 Correct 132 ms 10296 KB Output is correct
3 Correct 137 ms 10528 KB Output is correct
4 Correct 132 ms 10456 KB Output is correct
5 Correct 132 ms 10144 KB Output is correct
6 Correct 136 ms 10536 KB Output is correct
7 Correct 161 ms 10232 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 10644 KB Output is correct
2 Correct 129 ms 10196 KB Output is correct
3 Correct 126 ms 10404 KB Output is correct
4 Correct 503 ms 47084 KB Output is correct
5 Correct 252 ms 13212 KB Output is correct
6 Correct 137 ms 10424 KB Output is correct
7 Correct 127 ms 10328 KB Output is correct
8 Correct 138 ms 10380 KB Output is correct
9 Correct 142 ms 10412 KB Output is correct
10 Correct 472 ms 47096 KB Output is correct
11 Correct 442 ms 29488 KB Output is correct
12 Correct 127 ms 10180 KB Output is correct
13 Correct 132 ms 10296 KB Output is correct
14 Correct 137 ms 10528 KB Output is correct
15 Correct 132 ms 10456 KB Output is correct
16 Correct 132 ms 10144 KB Output is correct
17 Correct 136 ms 10536 KB Output is correct
18 Correct 161 ms 10232 KB Output is correct
19 Correct 434 ms 20984 KB Output is correct
20 Correct 619 ms 40800 KB Output is correct
21 Correct 284 ms 15040 KB Output is correct
22 Correct 260 ms 14784 KB Output is correct
23 Correct 616 ms 50152 KB Output is correct
24 Correct 663 ms 65764 KB Output is correct
25 Correct 843 ms 84624 KB Output is correct