Submission #94217

#	Time	Username	Problem	Language	Result	Execution time	Memory
94217		zeyad49	Teams (CEOI11_tea)	Java	80 / 100	2637 ms	183020 KiB

tea

import java.io.*;
import java.util.*;

class tea{

	static int INF=(int)1e9;
	static Integer[]indices;
	static int n,a[];
	static 	int []dp,nxt,ceil;
	
	static void check(int limit) {
		int last=n;
		for(int i=n-1;i>=0;i--) {
			int x=a[indices[i]];
			dp[i]=0;
			
			ceil[i]=last;
			if(i+x>n)
				continue;
		
			int first=ceil[x+i];
			if(first-i>limit)
				continue;
			dp[i]=dp[first]+1;
			nxt[i]=first;
			if(dp[i]>=dp[last]) {
				
				last=i;
			}
			ceil[i]=last;
			
		}
		
		
	}
	public static void main(String[] args) throws IOException {
		InputReader sc=new InputReader(System.in);
		PrintWriter out=new PrintWriter(System.out);
		 n=sc.nextInt();
		indices=new Integer[n];
		int []cnt=new int [n];
		a=new int [n];
		dp=new int [n+1];
		ceil=new int [n+1];
		nxt=new int [n+1];
		int[][]adj=new int[n][];
		for(int i=0;i<n;i++) {
			a[i]=sc.nextInt();
			cnt[a[i]-1]++;
		}
		ceil[n]=n;
		for(int i=0;i<n;i++) {
			adj[i]=new int [cnt[i]];
		}
		for(int i=0;i<n;i++) {
			int x=a[i]-1;
			adj[x][--cnt[x]]=i;
		}
		
		for(int i=n-1,idx=0;i>=0;i--) {
			for(int x:adj[i])
				indices[idx++]=x;
		}
		
		
		check(n);
		int maxTeams=dp[0];
		int best=n;
		
		int lo=1,hi=n-1;
		
		while(lo<=hi) {
			int mid=lo+hi>>1;
			check(mid);
			if(dp[0]==maxTeams) {
				hi=mid-1;
				best=mid;
			}
			else
				lo=mid+1;
			
		}
		check(best);
		
		out.println(dp[0]);
		Queue<Integer> list=new LinkedList();
		for(int i=0;i<n;) {
			int j=nxt[i];
			while(i<j) {
				list.add(indices[i]+1);
				i++;
			}
			out.print(list.size());
			while(!list.isEmpty())
				out.print(" "+list.poll());
			out.println();
		}
		out.close();

	}
	static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }


}

Compilation message (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10