oj.uz

답안 #94217

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
94217 2019-01-16T17:29:34 Z zeyad49 Teams (CEOI11_tea) Java 11
80 / 100
 2500 ms 183020 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;
	
	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

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

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 9588 KB Output is correct
2 Correct 75 ms 9632 KB Output is correct
3 Correct 74 ms 9720 KB Output is correct
4 Correct 76 ms 9732 KB Output is correct
5 Correct 75 ms 9848 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 9480 KB Output is correct
2 Correct 72 ms 9720 KB Output is correct
3 Correct 70 ms 9664 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 9668 KB Output is correct
2 Correct 72 ms 9756 KB Output is correct
3 Correct 72 ms 9604 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 102 ms 11324 KB Output is correct
2 Correct 107 ms 11680 KB Output is correct
3 Correct 117 ms 12020 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 11736 KB Output is correct
2 Correct 111 ms 11788 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 353 ms 36940 KB Output is correct
2 Correct 323 ms 38228 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 380 ms 39220 KB Output is correct
2 Correct 307 ms 36640 KB Output is correct
3 Correct 341 ms 38600 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1305 ms 142936 KB Output is correct
2 Correct 1160 ms 139828 KB Output is correct
3 Correct 1306 ms 141332 KB Output is correct

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2626 ms 183020 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2637 ms 172040 KB Time limit exceeded
2 Halted 0 ms 0 KB -