Submission #94215

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
94215	2019-01-16T16:41:42 Z	zeyad49	Teams (CEOI11_tea)	Java 11	20 / 100	2500 ms	173556 KB

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; //number of teams
	
	static void check(int limit) {
	
		
		int last=n;
		
		
		

		
		
		for(int i=n-1;i>=0;i--) {
			int x=a[indices[i]];
			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

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

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	70 ms	9720 KB	Output is correct
2	Correct	69 ms	9464 KB	Output is correct
3	Incorrect	73 ms	9552 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	73 ms	9632 KB	Output is correct
2	Correct	76 ms	9712 KB	Output is correct
3	Correct	69 ms	9656 KB	Output is correct

Subtask #3
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	75 ms	9696 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	106 ms	11588 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	104 ms	11656 KB	Output is correct
2	Correct	106 ms	11388 KB	Output is correct

Subtask #6
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	408 ms	34812 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	389 ms	40516 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1407 ms	145528 KB	Output is correct
2	Correct	1284 ms	141504 KB	Output is correct
3	Incorrect	1101 ms	135664 KB	Output isn't correct

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1324 ms	155224 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2808 ms	173556 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-