| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 94082 | 2019-01-15T20:48:52 Z | zeyad49 | Teams (CEOI11_tea) | Java 11 | 2500 ms | 191048 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)
break;
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 {
Scanner sc=new Scanner();
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<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 Scanner
{
BufferedReader br;
StringTokenizer st;
Scanner(){
br=new BufferedReader(new InputStreamReader(System.in));
}
Scanner(String fileName) throws FileNotFoundException{
br=new BufferedReader(new FileReader(fileName));
}
String next() throws IOException {
while(st==null || !st.hasMoreTokens())
st=new StringTokenizer(br.readLine());
return st.nextToken();
}
String nextLine() throws IOException {
return br.readLine();
}
int nextInt() throws IOException{
return Integer.parseInt(next());
}
long nextLong() throws NumberFormatException, IOException {
return Long.parseLong(next());
}
double nextDouble() throws NumberFormatException, IOException {
return Double.parseDouble(next());
}
}
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 182 ms | 16472 KB | Output is correct |
| 2 | Correct | 263 ms | 15476 KB | Output is correct |
| 3 | Incorrect | 174 ms | 15764 KB | Output isn't correct |
| 4 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 190 ms | 16204 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 193 ms | 15872 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 363 ms | 24136 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 397 ms | 26208 KB | Output is correct |
| 2 | Incorrect | 378 ms | 23720 KB | Output isn't correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1419 ms | 93608 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1421 ms | 101852 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 2702 ms | 161812 KB | Time limit exceeded |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 2896 ms | 191048 KB | Time limit exceeded |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 2562 ms | 128856 KB | Time limit exceeded |
| 2 | Halted | 0 ms | 0 KB | - |