| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 94207 |
2019-01-16T16:28:39 Z |
zeyad49 |
Teams (CEOI11_tea) |
Java 11 |
|
2500 ms |
222236 KB |
import java.io.*;
import java.util.*;
class tea{
static int INF=(int)1e9;
static Integer[]indices;
static int []cand;
static int n,a[];
static int ceiling(int x,int lo,int hi) {
int ans=-1;
while(lo<=hi) {
int mid=lo+hi>>1;
int idx=cand[mid];
if(idx>=x) {
ans=idx;
lo=mid+1;
}
else
hi=mid-1;
}
return ans;
}
static int[][] check(int limit) {
int []dp=new int [n+1]; //number of teams
int []nxt=new int [n+1];
Deque queue=new Deque(2*n);
int lo=0;
int size=0;
cand[size++]=n;
queue.insertfront(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.getFront();
if(j-i>limit) {
queue.deletefront();;
lo++;
}
else
break;
}
int first=ceiling(x+i,lo,size-1);
if(first==-1)
continue;
dp[i]=dp[first]+1;
nxt[i]=first;
if(dp[i]>=dp[queue.getRear()]) {
queue.insertrear(i);
cand[size++]=i;
}
}
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];
cand=new int [n+1];
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 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 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);
}
}
static class Deque
{
int arr[];
int front;
int rear;
int size;
public Deque(int size)
{
arr = new int[3*n];
front = -1;
rear = 0;
this.size = size;
}
boolean isFull()
{
return ((front == 0 && rear == size-1)||
front == rear+1);
}
// Checks whether Deque is empty or not.
boolean isEmpty ()
{
return (front == -1);
}
// Inserts an element at front
void insertfront(int key)
{
// If queue is initially empty
if (front == -1)
{
front = 0;
rear = 0;
}
// front is at first position of queue
else if (front == 0)
front = size - 1 ;
else // decrement front end by '1'
front = front-1;
// insert current element into Deque
arr[front] = key ;
}
// function to inset element at rear end
// of Deque.
void insertrear(int key)
{
// If queue is initially empty
if (front == -1)
{
front = 0;
rear = 0;
}
// rear is at last position of queue
else if (rear == size-1)
rear = 0;
// increment rear end by '1'
else
rear = rear+1;
// insert current element into Deque
arr[rear] = key ;
}
// Deletes element at front end of Deque
void deletefront()
{
// Deque has only one element
if (front == rear)
{
front = -1;
rear = -1;
}
else
// back to initial position
if (front == size -1)
front = 0;
else // increment front by '1' to remove current
// front value from Deque
front = front+1;
}
// Delete element at rear end of Deque
void deleterear()
{
// Deque has only one element
if (front == rear)
{
front = -1;
rear = -1;
}
else if (rear == 0)
rear = size-1;
else
rear = rear-1;
}
// Returns front element of Deque
int getFront()
{
return arr[front];
}
// function return rear element of Deque
int getRear()
{
return arr[rear];
}
}
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;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
78 ms |
9716 KB |
Output is correct |
| 2 |
Correct |
78 ms |
9584 KB |
Output is correct |
| 3 |
Correct |
77 ms |
9556 KB |
Output is correct |
| 4 |
Correct |
74 ms |
9452 KB |
Output is correct |
| 5 |
Correct |
78 ms |
9480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
77 ms |
9656 KB |
Output is correct |
| 2 |
Correct |
77 ms |
9660 KB |
Output is correct |
| 3 |
Correct |
76 ms |
9616 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
73 ms |
9600 KB |
Output is correct |
| 2 |
Correct |
71 ms |
9784 KB |
Output is correct |
| 3 |
Correct |
71 ms |
9580 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
112 ms |
13100 KB |
Output is correct |
| 2 |
Correct |
122 ms |
14368 KB |
Output is correct |
| 3 |
Correct |
133 ms |
13800 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
123 ms |
13308 KB |
Output is correct |
| 2 |
Correct |
117 ms |
12988 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
378 ms |
48660 KB |
Output is correct |
| 2 |
Correct |
409 ms |
50764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
460 ms |
51204 KB |
Output is correct |
| 2 |
Correct |
431 ms |
50992 KB |
Output is correct |
| 3 |
Correct |
421 ms |
49264 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2378 ms |
210672 KB |
Output is correct |
| 2 |
Execution timed out |
2614 ms |
167932 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2519 ms |
173204 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2604 ms |
222236 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
