oj.uz

Submission #335525

# Submission time Handle Problem Language Result Execution time Memory
335525 2020-12-13T01:25:11 Z KWang31 Nice sequence (IZhO18_sequence) Java 11
0 / 100
 126 ms 9872 KB 
import java.io.*; import java.util.*;
public class sequence{
  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=1000000;
    
    public static void main(String[] args){
        
        FastReader br=new FastReader();
        int T=br.nextInt();
        while(T>0){
            T--;
            int N=br.nextInt(); int M=br.nextInt();
            
            int d=gcd(N,M); int n=N/d; int m=M/d;
            
            if((long) n*m==1){
                
                System.out.println(M-1);
                StringBuilder sb=new StringBuilder();
                for (int i = 1; i < M; i++) {
                    sb.append(1+" ");
                }
                System.out.println(sb.toString()); continue;
            }
            int[] psa=new int[n+m-1]; //psa[0]=0
            int cur=n-1;
            for (int i = 0; i < n+m-2; i++) {
                
                if(cur>=m){
                    psa[cur-m]=psa[cur]-1; cur-=m;
                }else{
                    psa[cur+n]=psa[cur]-1; cur+=n;
                }
            }
            for (int i = n+m-2; i >=0; i--) {
                psa[i]-=psa[0];
            }
            long[] ans=new long[N+M-d];
            
            boolean[] pos=new boolean[n+m-1];
            boolean[] neg=new boolean[n+m-1];
            for (int i = 1; i < n+m-1; i++) {
                if(psa[i]-psa[i-1]>0){
                    pos[psa[i]-psa[i-1]]=true;
                }else{
                    neg[psa[i-1]-psa[i]]=true;
                }
            }
            
            if(d==1){
                for (int j = 0; j < n+m-1; j++) {
                    for (int i = 0; i < d; i++) {
                        ans[j*d+i]=(long) MOD*i+psa[j];
                    
                    }
                }
            }else{
                int c=1; while((d-1)*c<=n+m && pos[(d-1)*c])c++;
                int z=1; while((d-1)*z<=n+m && neg[(d-1)*z])z++;
                c=Math.min(c,-z);
                for (int j = 0; j < n+m-1; j++) {
                    for (int i = 0; i < d; i++) {
                        ans[j*d+i]=(long) c*i+psa[j];
                    
                    }
                }
            }
            
            System.out.println(N+M-d-1);
            
            if(N+M-d>1){
                StringBuilder sb=new StringBuilder();
                for (int i = 1; i < N+M-d; i++) {
                    sb.append((long) (ans[i]-ans[i-1])+" ");
                }
                System.out.println(sb.toString());
            }
        }
        
        
    }
    public static int gcd(int a, int b){//Assumes a>b
        if(b==0)return a;
        return gcd(b,a%b);
    }
    
    
}
//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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 9704 KB Ok
2 Correct 122 ms 9708 KB Ok
3 Correct 118 ms 9704 KB Ok
4 Correct 117 ms 9872 KB Ok
5 Correct 123 ms 9680 KB Ok
6 Correct 122 ms 9704 KB Ok
7 Correct 120 ms 9708 KB Ok
8 Runtime error 74 ms 8552 KB Execution failed because the return code was nonzero
9 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 117 ms 9600 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 9704 KB Ok
2 Correct 126 ms 9636 KB Ok
3 Runtime error 112 ms 9708 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 114 ms 9580 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 9704 KB Ok
2 Correct 122 ms 9708 KB Ok
3 Correct 118 ms 9704 KB Ok
4 Correct 117 ms 9872 KB Ok
5 Correct 123 ms 9680 KB Ok
6 Correct 122 ms 9704 KB Ok
7 Correct 120 ms 9708 KB Ok
8 Runtime error 74 ms 8552 KB Execution failed because the return code was nonzero
9 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 9704 KB Ok
2 Correct 122 ms 9708 KB Ok
3 Correct 118 ms 9704 KB Ok
4 Correct 117 ms 9872 KB Ok
5 Correct 123 ms 9680 KB Ok
6 Correct 122 ms 9704 KB Ok
7 Correct 120 ms 9708 KB Ok
8 Runtime error 74 ms 8552 KB Execution failed because the return code was nonzero
9 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 9704 KB Ok
2 Correct 122 ms 9708 KB Ok
3 Correct 118 ms 9704 KB Ok
4 Correct 117 ms 9872 KB Ok
5 Correct 123 ms 9680 KB Ok
6 Correct 122 ms 9704 KB Ok
7 Correct 120 ms 9708 KB Ok
8 Runtime error 74 ms 8552 KB Execution failed because the return code was nonzero
9 Halted 0 ms 0 KB -