oj.uz

Submission #336161

# Submission time Handle Problem Language Result Execution time Memory
336161 2020-12-14T22:52:50 Z KWang31 Fun Tour (APIO20_fun) Java 11
31 / 100
 550 ms 40400 KB 
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
        if(sz==2){
          int[] p=new int[2]; int cur=0;
          if(arl[1].size()>arl[0].size()){
             cur=1;
          }
          for(int done=0; done<N; done++){
             a[done]=arl[cur].get(p[cur]).vtx; p[cur]++; cur=1-cur;
          }
          return a;
        }
        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;  y=0;
        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;
          }
        }
        //System.out.println(arl[0].size()+" "+cur);
        a[0]=arl[cur].get(p[cur]).vtx; p[cur]++;
        //System.out.println(a[0]+".."+cur);
        //System.out.println(Arrays.toString(p));
        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(x==-5 && y==-5){
               a[done]=arl[cur].get(p[cur]).vtx; return a;
            }else if(2*(arl[(cur+1)%3].size()-p[(cur+1)%3])>=N-done+1 && y<=a[done-1]){
              cur=(cur+1)%3;
            }else if(2*(arl[(cur+2)%3].size()-p[(cur+2)%3])>=N-done+1 && x<=a[done-1]){
              cur=(cur+2)%3;
            }else if(x>=y){
              cur=(cur+1)%3;
              
            }else{
              cur=(cur+2)%3;
            }
            //System.out.println(done+" "+cur+" "+p[cur]);
            a[done]=arl[cur].get(p[cur]).vtx; p[cur]++;
        }
        
        return a;
    }
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 8684 KB Output is correct
2 Correct 74 ms 8424 KB Output is correct
3 Correct 74 ms 8428 KB Output is correct
4 Correct 76 ms 8812 KB Output is correct
5 Correct 76 ms 8512 KB Output is correct
6 Correct 75 ms 8684 KB Output is correct
7 Correct 75 ms 8556 KB Output is correct
8 Correct 76 ms 8528 KB Output is correct
9 Correct 76 ms 8684 KB Output is correct
10 Correct 78 ms 8684 KB Output is correct
11 Correct 74 ms 8556 KB Output is correct
12 Correct 73 ms 8556 KB Output is correct
13 Correct 75 ms 8428 KB Output is correct
14 Correct 76 ms 8656 KB Output is correct
15 Correct 90 ms 8680 KB Output is correct
16 Correct 74 ms 8556 KB Output is correct
17 Correct 75 ms 8556 KB Output is correct
18 Correct 75 ms 8684 KB Output is correct
19 Correct 76 ms 8684 KB Output is correct
20 Correct 76 ms 8428 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 8684 KB Output is correct
2 Correct 74 ms 8424 KB Output is correct
3 Correct 74 ms 8428 KB Output is correct
4 Correct 76 ms 8812 KB Output is correct
5 Correct 76 ms 8512 KB Output is correct
6 Correct 75 ms 8684 KB Output is correct
7 Correct 75 ms 8556 KB Output is correct
8 Correct 76 ms 8528 KB Output is correct
9 Correct 76 ms 8684 KB Output is correct
10 Correct 78 ms 8684 KB Output is correct
11 Correct 74 ms 8556 KB Output is correct
12 Correct 73 ms 8556 KB Output is correct
13 Correct 75 ms 8428 KB Output is correct
14 Correct 76 ms 8656 KB Output is correct
15 Correct 90 ms 8680 KB Output is correct
16 Correct 74 ms 8556 KB Output is correct
17 Correct 75 ms 8556 KB Output is correct
18 Correct 75 ms 8684 KB Output is correct
19 Correct 76 ms 8684 KB Output is correct
20 Correct 76 ms 8428 KB Output is correct
21 Correct 83 ms 8540 KB Output is correct
22 Correct 79 ms 8556 KB Output is correct
23 Correct 80 ms 8428 KB Output is correct
24 Correct 98 ms 9604 KB Output is correct
25 Correct 78 ms 8428 KB Output is correct
26 Correct 79 ms 8556 KB Output is correct
27 Correct 78 ms 8524 KB Output is correct
28 Correct 74 ms 8684 KB Output is correct
29 Incorrect 122 ms 10528 KB Repeated index
30 Halted 0 ms 0 KB -

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 8424 KB Output is correct
2 Correct 74 ms 8428 KB Output is correct
3 Correct 76 ms 8812 KB Output is correct
4 Correct 76 ms 8512 KB Output is correct
5 Correct 75 ms 8684 KB Output is correct
6 Correct 75 ms 8556 KB Output is correct
7 Correct 76 ms 8528 KB Output is correct
8 Correct 76 ms 8684 KB Output is correct
9 Correct 83 ms 8540 KB Output is correct
10 Correct 79 ms 8556 KB Output is correct
11 Correct 80 ms 8428 KB Output is correct
12 Correct 98 ms 9604 KB Output is correct
13 Correct 78 ms 8428 KB Output is correct
14 Correct 79 ms 8556 KB Output is correct
15 Correct 78 ms 8524 KB Output is correct
16 Correct 99 ms 9540 KB Output is correct
17 Correct 111 ms 9940 KB Output is correct
18 Correct 550 ms 40400 KB Output is correct
19 Correct 137 ms 10004 KB Output is correct
20 Correct 163 ms 10280 KB Output is correct
21 Correct 172 ms 10756 KB Output is correct
22 Correct 250 ms 13472 KB Output is correct
23 Correct 409 ms 17496 KB Output is correct
24 Correct 406 ms 18668 KB Output is correct
25 Correct 506 ms 30216 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 8424 KB Output is correct
2 Correct 74 ms 8428 KB Output is correct
3 Correct 78 ms 8684 KB Output is correct
4 Correct 74 ms 8556 KB Output is correct
5 Correct 73 ms 8556 KB Output is correct
6 Correct 75 ms 8428 KB Output is correct
7 Correct 74 ms 8684 KB Output is correct
8 Incorrect 122 ms 10528 KB Repeated index
9 Halted 0 ms 0 KB -

Subtask #5
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 8684 KB Output is correct
2 Correct 74 ms 8424 KB Output is correct
3 Correct 74 ms 8428 KB Output is correct
4 Correct 76 ms 8812 KB Output is correct
5 Correct 76 ms 8512 KB Output is correct
6 Correct 75 ms 8684 KB Output is correct
7 Correct 75 ms 8556 KB Output is correct
8 Correct 76 ms 8528 KB Output is correct
9 Correct 76 ms 8684 KB Output is correct
10 Correct 78 ms 8684 KB Output is correct
11 Correct 74 ms 8556 KB Output is correct
12 Correct 73 ms 8556 KB Output is correct
13 Correct 75 ms 8428 KB Output is correct
14 Correct 76 ms 8656 KB Output is correct
15 Correct 90 ms 8680 KB Output is correct
16 Correct 74 ms 8556 KB Output is correct
17 Correct 75 ms 8556 KB Output is correct
18 Correct 75 ms 8684 KB Output is correct
19 Correct 76 ms 8684 KB Output is correct
20 Correct 76 ms 8428 KB Output is correct
21 Correct 83 ms 8540 KB Output is correct
22 Correct 79 ms 8556 KB Output is correct
23 Correct 80 ms 8428 KB Output is correct
24 Correct 98 ms 9604 KB Output is correct
25 Correct 78 ms 8428 KB Output is correct
26 Correct 79 ms 8556 KB Output is correct
27 Correct 78 ms 8524 KB Output is correct
28 Correct 74 ms 8684 KB Output is correct
29 Incorrect 122 ms 10528 KB Repeated index
30 Halted 0 ms 0 KB -