oj.uz

Submission #335523

# Submission time Handle Problem Language Result Execution time Memory
335523 2020-12-13T01:20:31 Z KWang31 Nice sequence (IZhO18_sequence) Java 11
58 / 100
 544 ms 32124 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;
                }
            }
            int c=1; while(pos[c])c++;
            int z=1; while(neg[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) MOD*i+psa[j];
                    
                }
            }
            //System.out.println(Arrays.toString(ans));
            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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 9728 KB Ok
2 Correct 119 ms 9708 KB Ok
3 Correct 118 ms 9708 KB Ok
4 Correct 118 ms 9708 KB Ok
5 Correct 120 ms 9708 KB Ok
6 Correct 116 ms 9836 KB Ok
7 Correct 119 ms 9600 KB Ok
8 Correct 116 ms 9600 KB Ok
9 Correct 118 ms 9708 KB Ok
10 Correct 116 ms 9728 KB Ok
11 Correct 122 ms 9728 KB Ok
12 Correct 75 ms 8528 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 9584 KB Ok
2 Correct 120 ms 9492 KB Ok
3 Correct 127 ms 9580 KB Ok
4 Correct 117 ms 9600 KB Ok
5 Correct 118 ms 9740 KB Ok
6 Correct 340 ms 15956 KB Ok
7 Correct 328 ms 17392 KB Ok
8 Correct 307 ms 16656 KB Ok
9 Correct 341 ms 16236 KB Ok
10 Correct 305 ms 17000 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 9580 KB Ok
2 Correct 115 ms 9708 KB Ok
3 Correct 119 ms 9580 KB Ok
4 Correct 114 ms 9600 KB Ok
5 Correct 117 ms 9728 KB Ok
6 Correct 122 ms 9580 KB Ok
7 Correct 119 ms 9708 KB Ok
8 Correct 114 ms 9580 KB Ok
9 Correct 116 ms 9708 KB Ok
10 Correct 115 ms 9600 KB Ok
11 Correct 115 ms 9836 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 9648 KB Ok
2 Correct 119 ms 9688 KB Ok
3 Correct 122 ms 9692 KB Ok
4 Correct 120 ms 9652 KB Ok
5 Correct 117 ms 9708 KB Ok
6 Correct 449 ms 25612 KB Ok
7 Correct 480 ms 24584 KB Ok
8 Correct 511 ms 32124 KB Ok
9 Correct 544 ms 28192 KB Ok
10 Correct 371 ms 23752 KB Ok
11 Correct 530 ms 31264 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 9728 KB Ok
2 Correct 119 ms 9708 KB Ok
3 Correct 118 ms 9708 KB Ok
4 Correct 118 ms 9708 KB Ok
5 Correct 120 ms 9708 KB Ok
6 Correct 116 ms 9836 KB Ok
7 Correct 119 ms 9600 KB Ok
8 Correct 116 ms 9600 KB Ok
9 Correct 118 ms 9708 KB Ok
10 Correct 116 ms 9728 KB Ok
11 Correct 122 ms 9728 KB Ok
12 Correct 75 ms 8528 KB Ok
13 Correct 116 ms 9580 KB Ok
14 Correct 115 ms 9708 KB Ok
15 Correct 119 ms 9580 KB Ok
16 Correct 114 ms 9600 KB Ok
17 Correct 117 ms 9728 KB Ok
18 Correct 122 ms 9580 KB Ok
19 Correct 119 ms 9708 KB Ok
20 Correct 114 ms 9580 KB Ok
21 Correct 116 ms 9708 KB Ok
22 Correct 115 ms 9600 KB Ok
23 Correct 115 ms 9836 KB Ok
24 Correct 330 ms 16056 KB Ok
25 Correct 349 ms 16348 KB Ok
26 Correct 353 ms 16492 KB Ok
27 Correct 317 ms 16180 KB Ok
28 Correct 313 ms 15308 KB Ok
29 Correct 253 ms 11944 KB Ok
30 Correct 383 ms 16232 KB Ok
31 Correct 332 ms 16168 KB Ok
32 Correct 331 ms 16060 KB Ok
33 Correct 333 ms 17292 KB Ok
34 Correct 348 ms 16136 KB Ok
35 Correct 287 ms 16480 KB Ok
36 Correct 312 ms 16528 KB Ok
37 Correct 289 ms 16480 KB Ok
38 Correct 348 ms 16188 KB Ok
39 Correct 358 ms 16268 KB Ok
40 Correct 346 ms 16060 KB Ok
41 Correct 314 ms 16524 KB Ok
42 Correct 329 ms 16148 KB Ok
43 Correct 323 ms 15892 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 9728 KB Ok
2 Correct 119 ms 9708 KB Ok
3 Correct 118 ms 9708 KB Ok
4 Correct 118 ms 9708 KB Ok
5 Correct 120 ms 9708 KB Ok
6 Correct 116 ms 9836 KB Ok
7 Correct 119 ms 9600 KB Ok
8 Correct 116 ms 9600 KB Ok
9 Correct 118 ms 9708 KB Ok
10 Correct 116 ms 9728 KB Ok
11 Correct 122 ms 9728 KB Ok
12 Correct 75 ms 8528 KB Ok
13 Correct 117 ms 9584 KB Ok
14 Correct 120 ms 9492 KB Ok
15 Correct 127 ms 9580 KB Ok
16 Correct 117 ms 9600 KB Ok
17 Correct 118 ms 9740 KB Ok
18 Correct 340 ms 15956 KB Ok
19 Correct 328 ms 17392 KB Ok
20 Correct 307 ms 16656 KB Ok
21 Correct 341 ms 16236 KB Ok
22 Correct 305 ms 17000 KB Ok
23 Correct 116 ms 9580 KB Ok
24 Correct 115 ms 9708 KB Ok
25 Correct 119 ms 9580 KB Ok
26 Correct 114 ms 9600 KB Ok
27 Correct 117 ms 9728 KB Ok
28 Correct 122 ms 9580 KB Ok
29 Correct 119 ms 9708 KB Ok
30 Correct 114 ms 9580 KB Ok
31 Correct 116 ms 9708 KB Ok
32 Correct 115 ms 9600 KB Ok
33 Correct 115 ms 9836 KB Ok
34 Correct 330 ms 16056 KB Ok
35 Correct 349 ms 16348 KB Ok
36 Correct 353 ms 16492 KB Ok
37 Correct 317 ms 16180 KB Ok
38 Correct 313 ms 15308 KB Ok
39 Correct 253 ms 11944 KB Ok
40 Correct 383 ms 16232 KB Ok
41 Correct 332 ms 16168 KB Ok
42 Correct 331 ms 16060 KB Ok
43 Correct 333 ms 17292 KB Ok
44 Correct 348 ms 16136 KB Ok
45 Correct 287 ms 16480 KB Ok
46 Correct 312 ms 16528 KB Ok
47 Correct 289 ms 16480 KB Ok
48 Correct 348 ms 16188 KB Ok
49 Correct 358 ms 16268 KB Ok
50 Correct 346 ms 16060 KB Ok
51 Correct 314 ms 16524 KB Ok
52 Correct 329 ms 16148 KB Ok
53 Correct 323 ms 15892 KB Ok
54 Incorrect 464 ms 26224 KB Expected int32, but "-4144000002" found
55 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 9728 KB Ok
2 Correct 119 ms 9708 KB Ok
3 Correct 118 ms 9708 KB Ok
4 Correct 118 ms 9708 KB Ok
5 Correct 120 ms 9708 KB Ok
6 Correct 116 ms 9836 KB Ok
7 Correct 119 ms 9600 KB Ok
8 Correct 116 ms 9600 KB Ok
9 Correct 118 ms 9708 KB Ok
10 Correct 116 ms 9728 KB Ok
11 Correct 122 ms 9728 KB Ok
12 Correct 75 ms 8528 KB Ok
13 Correct 117 ms 9584 KB Ok
14 Correct 120 ms 9492 KB Ok
15 Correct 127 ms 9580 KB Ok
16 Correct 117 ms 9600 KB Ok
17 Correct 118 ms 9740 KB Ok
18 Correct 340 ms 15956 KB Ok
19 Correct 328 ms 17392 KB Ok
20 Correct 307 ms 16656 KB Ok
21 Correct 341 ms 16236 KB Ok
22 Correct 305 ms 17000 KB Ok
23 Correct 116 ms 9580 KB Ok
24 Correct 115 ms 9708 KB Ok
25 Correct 119 ms 9580 KB Ok
26 Correct 114 ms 9600 KB Ok
27 Correct 117 ms 9728 KB Ok
28 Correct 122 ms 9580 KB Ok
29 Correct 119 ms 9708 KB Ok
30 Correct 114 ms 9580 KB Ok
31 Correct 116 ms 9708 KB Ok
32 Correct 115 ms 9600 KB Ok
33 Correct 115 ms 9836 KB Ok
34 Correct 121 ms 9648 KB Ok
35 Correct 119 ms 9688 KB Ok
36 Correct 122 ms 9692 KB Ok
37 Correct 120 ms 9652 KB Ok
38 Correct 117 ms 9708 KB Ok
39 Correct 449 ms 25612 KB Ok
40 Correct 480 ms 24584 KB Ok
41 Correct 511 ms 32124 KB Ok
42 Correct 544 ms 28192 KB Ok
43 Correct 371 ms 23752 KB Ok
44 Correct 530 ms 31264 KB Ok
45 Correct 330 ms 16056 KB Ok
46 Correct 349 ms 16348 KB Ok
47 Correct 353 ms 16492 KB Ok
48 Correct 317 ms 16180 KB Ok
49 Correct 313 ms 15308 KB Ok
50 Correct 253 ms 11944 KB Ok
51 Correct 383 ms 16232 KB Ok
52 Correct 332 ms 16168 KB Ok
53 Correct 331 ms 16060 KB Ok
54 Correct 333 ms 17292 KB Ok
55 Correct 348 ms 16136 KB Ok
56 Correct 287 ms 16480 KB Ok
57 Correct 312 ms 16528 KB Ok
58 Correct 289 ms 16480 KB Ok
59 Correct 348 ms 16188 KB Ok
60 Correct 358 ms 16268 KB Ok
61 Correct 346 ms 16060 KB Ok
62 Correct 314 ms 16524 KB Ok
63 Correct 329 ms 16148 KB Ok
64 Correct 323 ms 15892 KB Ok
65 Incorrect 464 ms 26224 KB Expected int32, but "-4144000002" found
66 Halted 0 ms 0 KB -