| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 94085 | 2019-01-15T21:03:18 Z | zeyad49 | Teams (CEOI11_tea) | Java 11 | 2500 ms | 202976 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];
TreeSet<Integer> cand=new TreeSet();
Deque<Integer> queue=new LinkedList();
cand.add(n);
queue.add(n);
for(int i=n-1;i>=0;i--) {
int x=a[indices[i]];
if(i+x>n)
continue;
while(!queue.isEmpty()) {
int j=queue.peekFirst();
if(j-i>limit) {
queue.removeFirst();
cand.remove(j);
}
else
break;
}
Integer first=cand.ceiling(i+x);
if(first==null)
continue;
dp[i]=dp[first]+1;
nxt[i]=first;
if(dp[i]>=dp[queue.peekLast()]) {
queue.addLast(i);
cand.add(i);
}
// System.out.println(queue);
}
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];
a=new int [n];
for(int i=0;i<n;i++) {
a[i]=sc.nextInt();
indices[i]=i;
}
Arrays.sort(indices,Comparator.comparingInt(i->-a[i]));
int [][]x;
x=check(n);
int maxTeams=x[0][0];
int best=-1;
int lo=1,hi=n;
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 list=new Queue();
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 Queue
{
int back,front;
int []a;
int size=0;
public Queue()
{
a=new int [n];
}
public int poll()
{
size--;
return a[back++];
}
public void add(int x)
{
size++;
a[front++]=x;
}
public boolean isEmpty()
{
return size==0;
}
}
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 | 174 ms | 15488 KB | Output is correct |
| 2 | Correct | 177 ms | 15756 KB | Output is correct |
| 3 | Correct | 177 ms | 15584 KB | Output is correct |
| 4 | Correct | 178 ms | 15768 KB | Output is correct |
| 5 | Correct | 183 ms | 15864 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 192 ms | 15748 KB | Output is correct |
| 2 | Correct | 192 ms | 15768 KB | Output is correct |
| 3 | Correct | 194 ms | 16000 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 195 ms | 15652 KB | Output is correct |
| 2 | Correct | 198 ms | 16272 KB | Output is correct |
| 3 | Correct | 202 ms | 15684 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 327 ms | 23288 KB | Output is correct |
| 2 | Correct | 398 ms | 27148 KB | Output is correct |
| 3 | Correct | 366 ms | 27812 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 360 ms | 26160 KB | Output is correct |
| 2 | Correct | 330 ms | 22684 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1187 ms | 65348 KB | Output is correct |
| 2 | Correct | 1295 ms | 95272 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1585 ms | 93544 KB | Output is correct |
| 2 | Correct | 1315 ms | 93072 KB | Output is correct |
| 3 | Correct | 1403 ms | 91668 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 2679 ms | 202976 KB | Time limit exceeded |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 2538 ms | 155432 KB | Time limit exceeded |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 2629 ms | 130220 KB | Time limit exceeded |
| 2 | Halted | 0 ms | 0 KB | - |