제출 #336104

#제출 시각아이디문제언어결과실행 시간메모리
336104KWang31즐거운 행로 (APIO20_fun)Java
0 / 100
95 ms9452 KiB
import java.util.*; public class fun { 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; } } public static int[] createFunTour(int N, int Q){ if(N==2){ int[] a=new int[2]; a[1]=1; return a; } int min=N; int ind=0; int sz=0; for (int i = 1; i < N; i++) { sz=grader.attractionsBehind(0,i); if(2*sz>N && sz<min){ min=sz; ind=i; } } int c=0; if(min!=N){ c=ind;//Centroid } int[] ch=new int[3]; Arrays.fill(ch,-1); sz=0; for (int i = 0; i < N; i++) { if(i==c)continue; if(grader.hoursRequired(c,i)==1){ ch[sz]=i; sz++; } } int x,y; ArrayList<Pair> arl[]=new ArrayList[3]; for(int i=0;i<3;i++){arl[i]=new ArrayList<>(); if(i<sz){arl[i].add(new Pair(ch[i],1));}} if(sz==3){ for (int i = 0; i < N; i++) { if(i==c || i==ch[0] || i==ch[1] || i==ch[2])continue; x=grader.hoursRequired(ch[0],i); y=grader.hoursRequired(ch[1],i); if(x<y){ arl[0].add(new Pair(i,x+1)); }else if(y<x){ arl[1].add(new Pair(i,y+1)); }else{ arl[2].add(new Pair(i,x-1)); } } }else{ for (int i = 0; i < N; i++) { if(i==c || i==ch[0] || i==ch[1])continue; x=grader.hoursRequired(ch[0],i); y=grader.hoursRequired(ch[1],i); if(x<y){ arl[0].add(new Pair(i,x+1)); }else{ arl[1].add(new Pair(i,y+1)); } } } int[] a=new int[N]; if(arl[0].size()==N/2){ arl[1].add(new Pair(c,-1)); }else{ arl[0].add(new Pair(c,-1)); } for(int i=0;i<3;i++){Collections.sort(arl[i]);}//Sort in descending order int[] p=new int[3];//Keeps current pointer int z=0; int cur=0;//We cannot use vertices from the same subtree twice in a row x=arl[0].get(p[0]).val; for(int i=1; i<3; i++){ if(!arl[i].isEmpty() && arl[i].get(0).val > x){ x=arl[i].get(0).val; cur=i; } } a[0]=arl[cur].get(p[cur]).vtx; p[cur]++; for(int done=1; done<N; done++){ if(p[(cur+1)%3]<arl[(cur+1)%3].size()){x=arl[(cur+1)%3].get(p[(cur+1)%3]).val;} else{x=-5;} if(p[(cur+2)%3]<arl[(cur+2)%3].size()){y=arl[(cur+2)%3].get(p[(cur+2)%3]).val;} else{y=-5;} if(2*(arl[(cur+1)%3].size()-p[(cur+1)%3])>=N-done && y<=a[done-1]){ cur=(cur+1)%3; }else if(2*(arl[(cur+2)%3].size()-p[(cur+2)%3])>=N-done && x<=a[done-1]){ cur=(cur+2)%3; }else if(x>y){ cur=(cur+1)%3; }else{ cur=(cur+2)%3; } a[done]=arl[cur].get(p[cur]).vtx; p[cur]++; } return a; } }

컴파일 시 표준 에러 (stderr) 메시지

Note: fun.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
#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...