| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 336089 | KWang31 | Fun Tour (APIO20_fun) | Java | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
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[] c=new int[3];
for(int done=0; done<N; done++){
if(p[0]<arl[0].size()){c[0]=arl[0].get(p[0]).val; }else{c[0]=-5;}
if(p[1]<arl[1].size()){c[1]=arl[1].get(p[1]).val;} else{c[1]=-5;}
if(sz==3 && p[2]<arl[2].size()){c[2]=arl[2].get(p[2]).val;} else{c[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]+1 && c[1-cur] <= a[done-1]){
c[2]=N*2;
}else if( cur!= 1 && arl[1].size()-p[1]>=arl[0].size()-p[0]+arl[2].size()-p[2]+1 && c[2-cur] <= a[done-1]){
c[1]=N*2;
}else if(cur!=0 && arl[0].size()-p[0]>=arl[1].size()-p[1]+arl[2].size()-p[2]+1 && c[3-cur] <= a[done-1]){
c[0]=N*2;
}
}
}
if(cur==-1){
if(c[0]>=c[1] && c[0]>=c[2]){
cur=0; a[0]=arl[0].get(p[0]).vtx; p[0]++;
}else if(c[1]>=c[0] && c[1]>=c[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(c[1]==-5 && c[2]==-5){
cur=0; a[done]=arl[0].get(p[0]).vtx; p[0]++;
}else if(c[1]>=z){
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(c[0]==-5 && c[2]==-5){
cur=1; a[done]=arl[1].get(p[1]).vtx; p[1]++;
}else if(c[0]>=c[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(c[0]>=c[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;
}
}