Submission #336096

#	Time	Username	Problem	Language	Result	Execution time	Memory
336096		KWang31	Fun Tour (APIO20_fun)	Java	31 / 100	645 ms	42068 KiB

fun

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[sz];
        for(int i=0;i<sz;i++){arl[i]=new ArrayList<>(); 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<sz;i++){Collections.sort(arl[i]);}//Sort in descending order
        int[] p=new int[sz];//Keeps current pointer
        int z=0;
        
        int cur=-1;//We cannot use vertices from the same subtree twice in a row
       int[] cc=new int[3];
        for(int done=0; done<N; done++){
            
            if(p[0]<arl[0].size()){cc[0]=arl[0].get(p[0]).val; }else{cc[0]=-5;}
            if(p[1]<arl[1].size()){cc[1]=arl[1].get(p[1]).val;}  else{cc[1]=-5;}
            if(sz==3 && p[2]<arl[2].size()){cc[2]=arl[2].get(p[2]).val;}  else{cc[2]=-5;}
            //System.out.println(done+" "+x+" "+y+" "+z);
            if(sz==3){//starting to alternate
            	if(cur>=0) {
            		if(cur!=2 && arl[2].size()-p[2] >= arl[1].size()-p[1] + arl[0].size()-p[0] && cc[1-cur] <= a[done-1]){
                	
            			cc[2]=N*2;
            		}else if( cur!= 1 && arl[1].size()-p[1]>=arl[0].size()-p[0]+arl[2].size()-p[2] && cc[2-cur] <= a[done-1]){
            			cc[1]=N*2;
            		}else if(cur!=0 && arl[0].size()-p[0]>=arl[1].size()-p[1]+arl[2].size()-p[2]  && cc[3-cur] <= a[done-1]){
            			cc[0]=N*2;
            		}
            	}
            }
            if(cur==-1){
                if(cc[0]>=cc[1] && cc[0]>=cc[2]){
                    cur=0; a[0]=arl[0].get(p[0]).vtx; p[0]++;
                }else if(cc[1]>=cc[0] && cc[1]>=cc[2]){
                    cur=1;a[0]=arl[1].get(p[1]).vtx; p[1]++;
                }else{
                    cur=2;a[0]=arl[2].get(p[2]).vtx; p[2]++;
                }
            }else{
                if(cur==0){
                    if(cc[1]==-5 && cc[2]==-5){
                        cur=0; a[done]=arl[0].get(p[0]).vtx; p[0]++;
                    }else if(cc[1]>=cc[2]){
                        cur=1; a[done]=arl[1].get(p[1]).vtx; p[1]++;
                    }else{
                        cur=2; a[done]=arl[2].get(p[2]).vtx; p[2]++;
                    }
                }else if(cur==1){
                    if(cc[0]==-5 && cc[2]==-5){
                        cur=1; a[done]=arl[1].get(p[1]).vtx; p[1]++;
                    }else if(cc[0]>=cc[2]){
                         cur=0; a[done]=arl[0].get(p[0]).vtx; p[0]++;
                    }else{
                        cur=2; a[done]=arl[2].get(p[2]).vtx; p[2]++;
                    }
                }else{
                    if(cc[0]==-5 && cc[1]==-5){
                      cur=2; a[done]=arl[2].get(p[2]).vtx; p[2]++;
                    }else if(cc[0]>=cc[1]){
                         cur=0; a[done]=arl[0].get(p[0]).vtx; p[0]++;
                    }else{
                        cur=1; a[done]=arl[1].get(p[1]).vtx; p[1]++;
                    }
                }
            }
           // System.out.println(done+" "+a[done]);
        }
        
        return a;
    }
}

Compilation message (stderr)

Note: fun.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

• Subtask 1: 10 / 10
• Subtask 2: 0 / 16
• Subtask 3: 21 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34