Submission #476812

#	Time	Username	Problem	Language	Result	Execution time	Memory
476812		KWang31	Sob (COCI19_sob)	Java	110 / 110	843 ms	84624 KiB

sob

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 / 10
• Subtask 2: 29 / 29
• Subtask 3: 39 / 39
• Subtask 4: 32 / 32