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]];
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.
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
73 ms |
9592 KB |
Output is correct |
| 2 |
Correct |
75 ms |
9612 KB |
Output is correct |
| 3 |
Correct |
75 ms |
9648 KB |
Output is correct |
| 4 |
Correct |
75 ms |
9708 KB |
Output is correct |
| 5 |
Correct |
77 ms |
9600 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
78 ms |
9816 KB |
Output is correct |
| 2 |
Correct |
74 ms |
9716 KB |
Output is correct |
| 3 |
Correct |
73 ms |
9800 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
74 ms |
9700 KB |
Output is correct |
| 2 |
Correct |
75 ms |
9644 KB |
Output is correct |
| 3 |
Correct |
71 ms |
9496 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
116 ms |
11340 KB |
Output is correct |
| 2 |
Correct |
119 ms |
11792 KB |
Output is correct |
| 3 |
Correct |
109 ms |
11384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
107 ms |
11712 KB |
Output is correct |
| 2 |
Correct |
135 ms |
11460 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
333 ms |
35748 KB |
Output is correct |
| 2 |
Correct |
329 ms |
38148 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
362 ms |
37604 KB |
Output is correct |
| 2 |
Correct |
290 ms |
35280 KB |
Output is correct |
| 3 |
Correct |
375 ms |
39596 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1174 ms |
144540 KB |
Output is correct |
| 2 |
Correct |
1039 ms |
136964 KB |
Output is correct |
| 3 |
Correct |
1226 ms |
139500 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1613 ms |
156836 KB |
Output is correct |
| 2 |
Correct |
1610 ms |
207088 KB |
Output is correct |
| 3 |
Execution timed out |
2584 ms |
171564 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2660 ms |
171136 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
