540 - Team Queue

[wjomlex]

Yeah... is there any particularly tricky input? I'm assuming I have just a simple error. I'm also getting WA and would appreciate some input/output

Code: Select all

import java.util.*;

public class Main
{
	public static void main(String args[])
	{
		Scanner scan = new Scanner(System.in);
		int cases = 0;

		while(true)
		{
			cases++;
			int t = scan.nextInt();

			if(t == 0)
				break;

			int[] h = new int[1000005];

			for(int i=0;i < t;i++)
			{
				int n = scan.nextInt();

				for(int j=0;j < n;j++)
					h[scan.nextInt()] = i;
			}

			Node head = null;
			Node tail = null;
			Node[] p = new Node[t];

			System.out.println("Scenario #" + cases);

			//process
			while(true)
			{
				String str = scan.next();

				if(str.equals("STOP"))
					break;

				if(str.equals("ENQUEUE"))
				{
					int in = scan.nextInt();

					//System.out.println(in + " belongs to team " + h[in]);

					if(head == null)
					{
						//System.out.println("New head");
						p[h[in]] = head = tail = new Node(in, null);
					}
					else if(p[h[in]] == null)
					{
						//System.out.println("First element of team " + h[in]);
						tail.next = p[h[in]] = new Node(in, null);
						tail = p[h[in]];
					}
					else
					{
						//System.out.println("Adding to back of team " + h[in]);
						Node tmp = new Node(in, p[h[in]].next);
						if(tmp.next == null)
							tail = tmp;
						p[h[in]].next = tmp;
						p[h[in]] = tmp;
						//System.out.println("So the new tail end is " + p[h[in]].n);
					}
				}
				else
				{
					System.out.println(head.n);
					if(head.next != null && h[head.n] == h[head.next.n])
						p[h[head.n]] = head.next;
					else
						p[h[head.n]] = null;

					head = head.next;

					if(head == null)
						tail = null;
				}
			}
			System.out.println();
		}
	}
}


class Node
{
	public int n;
	public Node next;

	public Node(int in, Node inext)
	{
		n = in;
		next = inext;
	}
}

[Jehad Uddin]

i have used stl vector and its not fast enough, how can i reduce time ?

Code: Select all

#include<iostream>
#include<vector>
#include<map>
#include<queue>
#include<string>

using namespace std;

vector<int>q[200005];

int pos[1200];
int no[1000005];
int now;
int t;
int head;


int main()
{
    int i,j,k,l,m,n,u,v;
    int tst=0;
    char str1[200],str2[200],str3[200];
    while(scanf("%d",&t)==1&&t)
    {
        tst++;
        printf("Scenario #%d\n",tst);
        memset(no,0,sizeof(no));
        memset(pos,0,sizeof(no));
        for(i=1;i<=t;i++)
        {
            scanf("%d",&j);
            for(k=1;k<=j;k++)
            {
                scanf("%d",&l);
                no[l]=i;
            }
        }
        now=1;
        head=1;
        while(scanf("%s",&str1)==1)
        {
            if(strcmp(str1,"STOP")==0) break;

            if(strcmp(str1,"ENQUEUE")==0){
                scanf("%d",&n);
                u=no[n];
                v=pos[u];
                if(v==0)
                {
                    v=now++;
                    pos[u]=v;
                    q[v].push_back(n);
                }
                else
                {
                    q[v].push_back(n);
                }

            }
            else if(strcmp(str1,"DEQUEUE")==0){

                if(head<now){
                    u=0;
                    v=q[head][u];
                    printf("%d\n",v);
                    if(q[head].size()!=0){

                        q[head].erase(q[head].begin()+u);
                        if(q[head].size()==0) head++,pos[no[v]]=0;

                    }
                }


            }


        }

        if(head<now)
        for(i=head;i<=now;i++)  q[i].clear();


        printf("\n");
    }

    return 0;
}

[amishera]

I have a question. Any help would be greatly appreciated on this. I did straightforwardly for mapping team members to team. Like I created a big array with 1M entry, where the index is the member and array value is the team. What could be the elegant way to map this? I tried using bst for hashing but it had TLE. So I had to switch to array.

[helloneo]

I have a question. Any help would be greatly appreciated on this. I did straightforwardly for mapping team members to team. Like I created a big array with 1M entry, where the index is the member and array value is the team. What could be the elegant way to map this? I tried using bst for hashing but it had TLE. So I had to switch to array.

I used STL map like this..

map<int, int> team;
team = j ; // the team of member i is j

I think BST is even better. Maybe your TLE was caused by other reasons..

[Shafaet_du]

I implemented my own queue for this problem using linked list. Its only the 2nd problem in uva that i solved using linked-list,the other one is 112

[jspac]

Could anyone tell me what is wrong with my program,
or just give me a test case for which my program fails?
I'm getting WA and don't know why..

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void)
{
	char str[10];
	int s, t, T, k, K, num, head, tail, X, *queue, *exists;
	const int MAX_NUM = 1000000;
	const int SZ_QUEUE = MAX_NUM * sizeof(int);
	const int SZ_EXISTS = MAX_NUM * sizeof(int);
	
	queue = (int *)malloc(SZ_QUEUE);
	exists = (int *)malloc(SZ_EXISTS);
	
	s = 0;
	while (scanf("%d %*[ \n\r\t]", &T) == 1 && T)
	{
		printf("Scenario #%d\n", ++s);
		
		num = 0;
		memset((void *)exists, 0, SZ_EXISTS);
		for (t = 0; t < T; t++)
		{
			scanf("%d %*[ \n\r\t]", &K);
			for (k = 0; k < K; k++)
			{
				scanf("%d %*[ \n\r\t]", queue + num);
				exists[queue[num]] = 1;
				num++;
			}
		}
		head = 0;
		tail = num - 1;
		
		while (scanf("%[A-Z]", str) == 1 && str[0] != 'S')
		{
			scanf("%*[ \n\r\t]");
			if (str[0] == 'E')
			{
				scanf("%d %*[ \n\r\t]", &X);
				if (!exists[X])
				{
					tail = (tail + 1) % MAX_NUM;
					queue[tail] = X;
					exists[X] = 1;
					num++;
				}
			}
			else if (num)
			{
				exists[queue[head]] = 0;
				printf("%d\n", queue[head]);
				num--;
				if (num) head = (head + 1) % MAX_NUM;
				else { head = 0; tail = -1; }
			}
		}
		scanf("%*[ \n\r\t]");
		
		printf("\n");
	}
	
	return 0;
}

[tiendaotd]

After 10 submit , finally I got AC for this problems. I post some I/O that's useful for my debug here so it might help ones who's searching for critical I/O . To solved this problems I use an array of iterator, well it's quite weird for me that this's first time I do smthing like this.

Input :

Code: Select all

2
3 1 2 3
3 4 5 6
ENQUEUE 1
ENQUEUE 2
ENQUEUE 4
DEQUEUE
DEQUEUE
ENQUEUE 3
ENQUEUE 1
ENQUEUE 5
ENQUEUE 6
DEQUEUE
DEQUEUE
DEQUEUE
ENQUEUE 1
DEQUEUE
STOP
2
3 1 2 3
3 4 5 6
ENQUEUE 1
ENQUEUE 2
ENQUEUE 4
DEQUEUE
DEQUEUE
DEQUEUE
ENQUEUE 3
ENQUEUE 5
ENQUEUE 6
DEQUEUE
DEQUEUE
DEQUEUE
ENQUEUE 1
DEQUEUE
STOP
2
2 1 2
2 3 4
ENQUEUE 1
ENQUEUE 2
ENQUEUE 3
ENQUEUE 4
DEQUEUE
DEQUEUE
ENQUEUE 1
ENQUEUE 2
DEQUEUE
DEQUEUE
STOP
2
3 101 102 103
3 201 202 203
ENQUEUE 101
ENQUEUE 201
ENQUEUE 102
ENQUEUE 202
ENQUEUE 103
ENQUEUE 203
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
2
5 259001 259002 259003 259004 259005
6 260001 260002 260003 260004 260005 260006
ENQUEUE 259001
ENQUEUE 260001
ENQUEUE 259002
ENQUEUE 259003
ENQUEUE 259004
ENQUEUE 259005
DEQUEUE
DEQUEUE
ENQUEUE 260002
ENQUEUE 260003
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
2
2 3 4
1 5
ENQUEUE 3
ENQUEUE 5
ENQUEUE 4
DEQUEUE
DEQUEUE
DEQUEUE
STOP
0

Ouput :

Code: Select all

Scenario #1
1
2
4
5
6
3

Scenario #2
1
2
4
3
5
6
1

Scenario #3
1
2
3
4

Scenario #4
101
102
103
201
202
203

Scenario #5
259001
259002
259003
259004
259005
260001

Scenario #6
3
4
5

[draconian devil]

Getting Wrong Answer on this. Can anyone provide any test case.

Code: Select all

ACCEPTED

[brianfry713]

Try the I/O in the post before yours.

[draconian devil]

brianfry713, the code passes all test cases in here

[shiam]

You can try this case:

Code: Select all

3
3 1 2 3
3 11 12 13
3 21 22 23
ENQUEUE 1
DEQUEUE
ENQUEUE 12
ENQUEUE 2
ENQUEUE 23
ENQUEUE 11
DEQUEUE
ENQUEUE 3
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
0

MY Ac code ans is :

Code: Select all

Scenario #1
1
12
11
2
3
23

While your ans is :

Code: Select all

Scenario #1
1
12
11
23
0
0

[draconian devil]

thanks shiam vai.

[hpjhc]

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
typedef struct node
{
int n;
struct node* next;
}Node;

void enqueue(Node*);
int dequeue();
Node* newnode();
Node* first, *last;
Node *sign[100];
int a[1000000], p;
int main(void) {

int i, n, k, j, num, m;
char s[10];
Node *temp;
m = 0;
while(scanf("%d", &n), n)
{
m++;
printf("Scenario #%d\n", m);
first = last = NULL;
for(i = 0; i < 100; i++)
sign = NULL;
j = 0;
while(n--)
{
scanf("%d", &k);
for(i = 0; i < k; i++)
{
scanf("%d", &num);
a[num] = j;
}
j++;
}
while(1)
{
scanf("%s", s);
if(s[0] == 'S')
break;
if(s[0] == 'E')
{
scanf("%d", &num);
temp = newnode();
temp->n = num;
enqueue(temp);
}
else
{
printf("%d\n", dequeue());

}
}
while(first != NULL)
{
temp = first;
first = first->next;
free(temp);
}
printf("\n");
}
return 0;
}

void enqueue(Node *node)
{
Node *temp;
if(first == NULL)
{
first = last = node;
sign[a[node->n]] = first;
}
else
{
if(sign[a[node->n]] == NULL)
{
last->next = node;
last = node;
sign[a[node->n]] = last;
}
else
{
p = a[node->n];
if(sign[p] == last)
last = node;
temp = sign[p]->next;
sign[p]->next = node;
sign[p] = node;
node->next = temp;
}
}
}

int dequeue()
{
Node *temp;
int k;
if(first == sign[a[first->n]])
sign[a[first->n]] = NULL;
k = first->n;
temp = first->next;
free(first);
first = temp;
return k;
}

Node* newnode()
{
Node *temp = (Node *)malloc(sizeof(Node));
temp->next = NULL;
return temp;
}

[brianfry713]

There may be up to 1000 teams, why is your sign array size 100?

[hpjhc]

There may be up to 1000 teams, why is your sign array size 100?

You are right.Thank you very much. When I try 1000, still RTE, in fact, I tried 1000 before. But this time I try 1010, get AC , but the problen say it is up to 1000 teams, it is confusing !