# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
94211 | 2019-01-16T16:36:56 Z | zeyad49 | Teams (CEOI11_tea) | Java 11 | 2500 ms | 227344 KB |
import java.io.*; import java.util.*; class tea{ static int INF=(int)1e9; static Integer[]indices; static int n,a[]; static int[][] check(int limit) { int []dp=new int [n+1]; //number of teams int []nxt=new int [n+1]; int []ceil=new int [n+1]; ceil[n]=n; 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; } int [][]ans=new int [2][n]; ans[0]=dp; ans[1]=nxt; return ans; } 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]; int[][]adj=new int[n][]; for(int i=0;i<n;i++) { a[i]=sc.nextInt(); cnt[a[i]-1]++; } 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; } int [][]x; x=check(n); int maxTeams=x[0][0]; int best=n; int lo=1,hi=n-1; while(lo<=hi) { int mid=lo+hi>>1; x=check(mid); if(x[0][0]==maxTeams) { hi=mid-1; best=mid; } else lo=mid+1; } x=check(best); int []dp=x[0]; int []nxt=x[1]; 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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 76 ms | 9716 KB | Output is correct |
2 | Correct | 77 ms | 9592 KB | Output is correct |
3 | Correct | 74 ms | 9720 KB | Output is correct |
4 | Correct | 75 ms | 9728 KB | Output is correct |
5 | Correct | 69 ms | 9720 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 74 ms | 9804 KB | Output is correct |
2 | Correct | 78 ms | 9588 KB | Output is correct |
3 | Correct | 68 ms | 9544 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 78 ms | 9816 KB | Output is correct |
2 | Correct | 125 ms | 9700 KB | Output is correct |
3 | Correct | 70 ms | 9848 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 106 ms | 13180 KB | Output is correct |
2 | Correct | 107 ms | 13164 KB | Output is correct |
3 | Correct | 108 ms | 13352 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 106 ms | 13212 KB | Output is correct |
2 | Correct | 101 ms | 12692 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 393 ms | 50072 KB | Output is correct |
2 | Correct | 350 ms | 51260 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 377 ms | 50588 KB | Output is correct |
2 | Correct | 322 ms | 50696 KB | Output is correct |
3 | Correct | 408 ms | 51200 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1358 ms | 211672 KB | Output is correct |
2 | Correct | 1908 ms | 227344 KB | Output is correct |
3 | Correct | 2347 ms | 217704 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2527 ms | 195792 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2539 ms | 218512 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |