Submission #319133

#	Time	Username	Problem	Language	Result	Execution time	Memory
319133		KWang31	Carnival Tickets (IOI20_tickets)	Java	100 / 100	1842 ms	148972 KiB

tickets

import java.io.*; import java.util.*;
public class tickets {
    public static class Pair implements Comparable<Pair>{
        int val; int ind;
        public Pair(int a, int b){
            this.val=a; this.ind=b;
        }
        public int compareTo(Pair other){
            if(this.val<other.val)return -1;
            if(this.val>other.val)return 1;
            if(this.ind>other.ind)return -1;
            return 1;
        }
    }
    public static long find_maximum(int k, int[][] x){
        long ans=0;
        PriorityQueue<Pair> pq=new PriorityQueue<>();
        int n=x.length; int m=x[0].length;
        int[] lp=new int[n]; // rp = (N-1) - i + lp
        int[][] s=new int[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(s[i],-1);
        }
        Arrays.fill(lp,k-1);
        boolean[] b=new boolean[n];
        for(int i=0;i<n;i++) {
            
            for (int j = 0; j < k; j++) {
                ans-=x[i][j];
            }
            pq.add(new Pair(-x[i][k-1]-x[i][m-1],i));
        }
        
        for (int i = 0; i < k*n/2; i++) {
            Pair p=pq.poll();
            ans-=p.val; lp[p.ind]--;
            if(lp[p.ind]>=0){
                pq.add(new Pair(-x[p.ind][lp[p.ind]]-x[p.ind][m-k+lp[p.ind]],p.ind));
                //System.out.println(p.ind+" "+lp[p.ind]+" "+(-x[p.ind][lp[p.ind]]-x[p.ind][m-k+lp[p.ind]]));
            }
            
            
        }
        pq=new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            pq.add(new Pair(lp[i]+1,i));//Smallest lp values will start with +
        }
        
        int[] pt=new int[n];//Pointer
        for (int i = 1; i <= k; i++) {
            Arrays.fill(b,false);
            for (int j = 0; j < n/2; j++) {
                Pair p=pq.poll();
                b[p.ind]=true; s[p.ind][m-i+pt[p.ind]]=i-1;
            }
            pq=new PriorityQueue<>();
            for (int j = 0; j < n; j++) {
                if(!b[j]){
                    s[j][pt[j]]=i-1; pt[j]++; lp[j]--;
                    
                    
                }
                pq.add(new Pair(lp[j],j));
                
                
                
            }
        }
        
       //System.out.println(Arrays.toString(lp));
        
        grader.allocate_tickets(s);
        return ans;
    }

    
}

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23
• Subtask 7: 10 / 10