oj.uz

Submission #335522

# Submission time Handle Problem Language Result Execution time Memory
335522 2020-12-13T01:02:00 Z KWang31 Nice sequence (IZhO18_sequence) Java 11
15 / 100
 873 ms 21940 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;
            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];
            for (int i = 0; i < d; i++) {
                for (int j = 0; j < n+m-1; j++) {
                    ans[j*d+i]=(long) d*i+psa[j];
                }
            }
            //System.out.println(Arrays.toString(ans));
            System.out.println(N+M-d-1);
            
            for (int i = 1; i < N+M-d; i++) {
                System.out.print((long) ans[i]-ans[i-1]+" ");
            }
            if(N+M-d>1)System.out.println("");
        }
        
        
    }
    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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 9640 KB Ok
2 Correct 133 ms 9836 KB Ok
3 Correct 137 ms 9708 KB Ok
4 Correct 133 ms 9728 KB Ok
5 Correct 149 ms 9708 KB Ok
6 Correct 139 ms 9692 KB Ok
7 Correct 133 ms 9728 KB Ok
8 Correct 134 ms 9836 KB Ok
9 Correct 138 ms 9728 KB Ok
10 Correct 134 ms 9600 KB Ok
11 Correct 138 ms 9620 KB Ok
12 Correct 133 ms 9708 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 9516 KB Ok
2 Correct 125 ms 9808 KB Ok
3 Correct 121 ms 9680 KB Ok
4 Correct 127 ms 9708 KB Ok
5 Correct 137 ms 9712 KB Ok
6 Correct 580 ms 15576 KB Ok
7 Correct 777 ms 21940 KB Ok
8 Correct 591 ms 20808 KB Ok
9 Correct 873 ms 21240 KB Ok
10 Correct 812 ms 21492 KB Ok

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 9708 KB Ok
2 Correct 122 ms 9788 KB Ok
3 Correct 116 ms 9708 KB Ok
4 Correct 117 ms 9708 KB Ok
5 Incorrect 121 ms 9720 KB All the numbers must be nonzero
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 120 ms 9708 KB All the numbers must be nonzero
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 9640 KB Ok
2 Correct 133 ms 9836 KB Ok
3 Correct 137 ms 9708 KB Ok
4 Correct 133 ms 9728 KB Ok
5 Correct 149 ms 9708 KB Ok
6 Correct 139 ms 9692 KB Ok
7 Correct 133 ms 9728 KB Ok
8 Correct 134 ms 9836 KB Ok
9 Correct 138 ms 9728 KB Ok
10 Correct 134 ms 9600 KB Ok
11 Correct 138 ms 9620 KB Ok
12 Correct 133 ms 9708 KB Ok
13 Correct 117 ms 9708 KB Ok
14 Correct 122 ms 9788 KB Ok
15 Correct 116 ms 9708 KB Ok
16 Correct 117 ms 9708 KB Ok
17 Incorrect 121 ms 9720 KB All the numbers must be nonzero
18 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 9640 KB Ok
2 Correct 133 ms 9836 KB Ok
3 Correct 137 ms 9708 KB Ok
4 Correct 133 ms 9728 KB Ok
5 Correct 149 ms 9708 KB Ok
6 Correct 139 ms 9692 KB Ok
7 Correct 133 ms 9728 KB Ok
8 Correct 134 ms 9836 KB Ok
9 Correct 138 ms 9728 KB Ok
10 Correct 134 ms 9600 KB Ok
11 Correct 138 ms 9620 KB Ok
12 Correct 133 ms 9708 KB Ok
13 Correct 118 ms 9516 KB Ok
14 Correct 125 ms 9808 KB Ok
15 Correct 121 ms 9680 KB Ok
16 Correct 127 ms 9708 KB Ok
17 Correct 137 ms 9712 KB Ok
18 Correct 580 ms 15576 KB Ok
19 Correct 777 ms 21940 KB Ok
20 Correct 591 ms 20808 KB Ok
21 Correct 873 ms 21240 KB Ok
22 Correct 812 ms 21492 KB Ok
23 Correct 117 ms 9708 KB Ok
24 Correct 122 ms 9788 KB Ok
25 Correct 116 ms 9708 KB Ok
26 Correct 117 ms 9708 KB Ok
27 Incorrect 121 ms 9720 KB All the numbers must be nonzero
28 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 9640 KB Ok
2 Correct 133 ms 9836 KB Ok
3 Correct 137 ms 9708 KB Ok
4 Correct 133 ms 9728 KB Ok
5 Correct 149 ms 9708 KB Ok
6 Correct 139 ms 9692 KB Ok
7 Correct 133 ms 9728 KB Ok
8 Correct 134 ms 9836 KB Ok
9 Correct 138 ms 9728 KB Ok
10 Correct 134 ms 9600 KB Ok
11 Correct 138 ms 9620 KB Ok
12 Correct 133 ms 9708 KB Ok
13 Correct 118 ms 9516 KB Ok
14 Correct 125 ms 9808 KB Ok
15 Correct 121 ms 9680 KB Ok
16 Correct 127 ms 9708 KB Ok
17 Correct 137 ms 9712 KB Ok
18 Correct 580 ms 15576 KB Ok
19 Correct 777 ms 21940 KB Ok
20 Correct 591 ms 20808 KB Ok
21 Correct 873 ms 21240 KB Ok
22 Correct 812 ms 21492 KB Ok
23 Correct 117 ms 9708 KB Ok
24 Correct 122 ms 9788 KB Ok
25 Correct 116 ms 9708 KB Ok
26 Correct 117 ms 9708 KB Ok
27 Incorrect 121 ms 9720 KB All the numbers must be nonzero
28 Halted 0 ms 0 KB -