Submission #335522

#TimeUsernameProblemLanguageResultExecution timeMemory
335522KWang31Nice sequence (IZhO18_sequence)Java
15 / 100
873 ms21940 KiB
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!
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...