11995 - I Can Guess the Data Structure!

[sith]

Hello guys!
I've got runtime error
What is wrong with my solution (java)

Code: Select all

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

class Main {
    public static void main(String[] args) {                
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String line;
        try {
            while ((line = reader.readLine()) != null) {
                int actionCount = Integer.parseInt(line.trim());
                List<DataStructure> dataStructures = new ArrayList<DataStructure>();
                dataStructures.add(new PriorityQueueDataStructure());
                dataStructures.add(new QueueDataStructure());
                dataStructures.add(new StackDataStructure());

                for (int i = 0; i < actionCount; i++) {
                    StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

                    int action = Integer.parseInt(tokenizer.nextToken());
                    int value = Integer.parseInt(tokenizer.nextToken());


                    switch (action) {
                        case 1:
                            for (DataStructure dataStructure : dataStructures) {
                                dataStructure.add(value);
                            }
                            break;
                        case 2:
                            for (Iterator<DataStructure> iterator = dataStructures.iterator(); iterator.hasNext(); ) {
                                final DataStructure dataStructure = iterator.next();
                                if (dataStructure.take() != value) {
                                    iterator.remove();
                                }
                            }
                            break;
                    }
                }
                if (dataStructures.isEmpty()) {
                    System.out.println("impossible");
                }
                else if (dataStructures.size() > 1) {
                    System.out.println("not sure");
                }
                else {
                    System.out.println(dataStructures.iterator().next().name());
                }
            }
        }
        catch (IOException e) {
        }
    }


    static interface DataStructure {
        int take();

        void add(int value);

        String name();
    }

    static class StackDataStructure implements DataStructure {

        private Stack<Integer> stack = new Stack<Integer>();

        public int take() {
            return stack.pop();
        }

        public void add(final int value) {
            stack.add(value);
        }

        public String name() {
            return "stack";
        }
    }

    static class QueueDataStructure implements DataStructure {

        private Queue<Integer> queue = new LinkedList<Integer>();

        public int take() {
            return queue.poll();
        }

        public void add(final int value) {
            queue.add(value);
        }

        public String name() {
            return "queue";
        }
    }

    static class PriorityQueueDataStructure implements DataStructure {

        private PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(256,new Comparator<Integer>() {
            public int compare(final Integer o1, final Integer o2) {
                return o2.compareTo(o1);
            }
        });

        public int take() {
            return priorityQueue.poll();
        }

        public void add(final int value) {
            priorityQueue.add(value);
        }

        public String name() {
            return "priority queue"; 
        }
    }
}

[brianfry713]

Check if the data structure is empty before you remove an element.

[sith]

Thanks
But now I've got WA

Code: Select all

AC

[brianfry713]

Doesn't match the sample I/O.

[sith]

Thanks it works!

[naved92]

Can anyone help me?I m continuously getting runtime error...

Code: Select all

removed after AC

[ramoto]

Hello guys!
I've got wrong answer
What is wrong with my java solution?

Code: Select all

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main {
	public static void main(String[] args) throws IOException
	{
			
		int qtd;
		
		boolean isStack = true;
		boolean isQueue = true;
		boolean isQueueP = true;
		
		String temp;
			
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer stringtoken;
		
		String linha;
		
		linha = br.readLine();
		
		qtd = Integer.parseInt(linha);
		
		
		while(qtd > 0)
		{	
			qtd = Integer.parseInt(linha);
			
			int[] stack = new int[qtd];
			int[] queue = new int[qtd];
			int[] queuep = new int[qtd];
				
			int last = -1;
			int first = 0;
			int max = 0;
			
			int istack = 0;
			int iqueue = 0;
			int iqueuep = 0;
			
				
			for(int i = 0; i < qtd; i++)
			{
				temp = br.readLine();
				stringtoken = new StringTokenizer(temp);
				int op = Integer.parseInt(stringtoken.nextToken());
				int el = Integer.parseInt(stringtoken.nextToken());
				if (el < 0) {
					el = el * -1;
				}
				
				if(isStack)
				{
					if(op == 1)
					{
						stack[istack] = el;
						last++;
						istack++;
					}
					else
					{
						if (last == -1) {
							isStack = false;
						}
						else if(el == stack[last] && istack != 0)
						{
							last--;
						}
						else
						{
							isStack = false;
						}
						
					}
				}
				if(isQueue)
				{
					if(op == 1)
					{
						queue[iqueue] = el;
						iqueue++;
					}
					else
					{
						if(el == queue[first] && iqueue != 0)
						{
							first++;
						}
						else
						{
							isQueue = false;
						}
						
					}
				}
				if(isQueueP)
				{
					if(op == 1)
					{
						queuep[iqueuep] = el;
						iqueuep++;
						
						if(el > max)
						{
							max = el;
						}
					}
					else
					{	
						if(el == max && iqueuep != 0)
						{					
							int max_temp = max;
							
							max = 0;
							
							for(int j = 0; j < iqueuep; j++)
							{
								if(queuep[j] > max && queuep[j] != max_temp)
								{
									max = queuep[j]; 
								}
								
								if(queuep[j] == max_temp)
								{
									queuep[j] = -1;
								}
							}
							
						}
						else
						{
							isQueueP = false;
						}
						
					}
				}
			}
	        if((isStack && isQueue) || (isStack && isQueueP) || (isQueue && isQueueP))  
	        {
	        	System.out.println("not sure");
	        }
	        else if(isStack)  
			{
	            System.out.println("stack");
			}
	        else if(isQueue) 
	        { 
	            System.out.println("queue");
	        }
	        else if(isQueueP) 
	        {
	        	System.out.println("priority queue");  
	        }
	        else  
	        {
	        	System.out.println("impossible");  
	        }
			
			isStack = true;
			isQueue = true;
			isQueueP = true;
			
			if(!br.ready())
			{
				qtd = -1;
			}
			else
			{
				linha = br.readLine();
			}
			
		}
			
	}
}

[brianfry713]

Input:

Code: Select all

8
1 3
1 2
2 2
2 3
1 1
1 4
2 4
2 1

stack

[mohsen1373]

Hi all, here is my code and it works for sample inputs and every other input I've made, but I get wrong answer !
Can anyone help me with that ?

Code: Select all

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
int main()
{
    int n,N;
    while( cin >> n )
    {
        N = n ;
        vector <int> v;
        int qu,st,ps;
        qu = st = ps =  0 ;
        int Max = -1 ;
        int twoCounter = 0 ;
        while( n-- )
        {
            int o, x;
            cin >> o >> x ;



            if( o == 1 )
            {
                v.push_back(x);
                if( x > Max )
                    Max = x ;

            }
            else
            {
                twoCounter++ ;
                for( int i = 0 ; i < v.size() ; i++ )
                {
                    if( v[i] == x )
                    {
                        if( i == v.size()-1 )
                            st++ ;

                        if( i == 0 )
                            qu++ ;

                        if( x == Max )
                            ps++ ;

                        v.erase(v.begin()+i,v.begin()+i+1);
                        if( ps == twoCounter )
                        {
                            Max = -1 ;
                            for( int j = 0 ; j < v.size() ; j++ )
                            {
                                if( v[j] > Max )
                                    Max = v[j];
                            }
                        }
                        break;
                    }
                }
            }
        }

        if( st == twoCounter && qu != twoCounter && ps != twoCounter )
            cout << "stack" << endl ;
        else if( st != twoCounter && qu == twoCounter && ps != twoCounter )
            cout << "queue" << endl ;
        else if( st != twoCounter && qu != twoCounter && ps == twoCounter )
            cout << "priority queue" << endl ;
        else if( st != twoCounter && qu != twoCounter && ps != twoCounter )
            cout << "impossible" << endl ;
        else
            cout << "not sure" << endl ;
    }
    return 0;
}

[brianfry713]

Input:

Code: Select all

4
1 1
1 2
1 2
2 2

AC output:
not sure

[zlshang]

hello guys!
I'v got wrong answer!
what's wrong with my codes(c++) PLZZZZ...

Code: Select all

#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <algorithm>
#include <string.h>
#include <iostream>
#include <cmath>
using namespace std;
int n,m,a[1000001],b[1000001],c[1000000],k,v;
bool  cmp(int x,int y)
{
	return a[x]<a[y];	
} 

int find( )
{
	int left=0,right=n-1,mid;
	while(left<right)
		{
			mid=(left+right)/2;	
			if(a[b[c[mid]]]<v) left=mid+1;
			else right=mid;	
		}	
	return left;
}
int main()
{
	while(scanf("%d%d",&n,&m)==2)
		{
			memset(a,1,sizeof(a));
			for(int i=1;i<=n;i++)
				{
					scanf("%d",&a[i]);
					b[i]=c[i]=i;
				}
			sort(b+1,b+n+1,cmp);
			for(int i=0;i<m;i++)
				{
					int p;
					scanf("%d%d",&k,&v);
					p=find();			
					if(p==0) 
						{
							if(a[b[0]]==v) printf("%d\n",a[b[k-1]]==v? b[k-1]:0);
							else if(a[b[1]]==v) printf("%d\n",a[b[k]]==v? b[k]:0);
							else printf("0\n");				
						}
					else 
						{
					
							if(a[b[p-1]]==v) printf("%d\n",a[b[p+k-2]]==v? b[p+k-2]:0);
							else if(a[b[p]]==v) printf("%d\n",a[b[p+k-1]]==v? b[p+k-1]:0);
							else if(a[b[p+1]]==v) printf("%d\n",a[b[p+k]]==v? b[p+k]:0);
							else printf("0\n");					
						}
				}
		}
		return 0;
  
}
/*
8 9
1 3 2 2 4 3 2 1
1 3
2 4
3 2
4 2

8 4
1 3 4 5 6 7 8 9
*/

[brianfry713]

Doesn't match the sample I/O. Is this code for problem #11995?

[zlshang]

Doesn't match the sample I/O. Is this code for problem #11995?

I so sorry! I forget that this problem #11995 I have solved. And this question is for the problem #11991. SORRY!! Thank you all the same

[ajmer]

Why do I get wrong answer? Seems to work on every sample input:

(C)

Code: Select all

AC

[brianfry713]

Here is the gift I/O from:
http://uva.onlinejudge.org/index.php?op ... ontest=278
Input:

Code: Select all

8
1 36
1 65
2 65
1 75
1 62
1 42
1 58
2 75
10
1 84
1 59
1 51
2 51
1 41
1 59
2 59
1 70
1 67
2 67
10
1 24
1 37
1 87
1 25
1 74
1 9
2 87
1 64
1 49
2 74
7
1 84
1 36
1 61
1 4
2 4
1 61
2 61
8
1 76
1 83
1 22
1 11
1 8
1 48
2 83
1 90
9
1 1
2 1
1 36
1 85
1 4
2 4
1 51
1 15
2 15
9
1 64
1 85
1 33
1 34
1 58
1 70
2 85
2 69
2 64
9
1 72
1 20
2 72
2 20
1 89
1 60
1 39
2 89
1 77
5
1 63
2 63
1 57
1 66
1 73
2
1 49
2 49
10
1 48
1 90
1 81
2 48
1 42
2 90
2 81
2 42
1 44
1 63
7
1 88
1 63
2 88
1 90
2 63
1 73
1 15
3
1 86
1 64
2 86
7
1 38
1 68
1 14
2 38
1 27
1 83
2 68

Output:

Code: Select all

priority queue
stack
priority queue
stack
priority queue
stack
impossible
not sure
not sure
not sure
queue
queue
not sure
queue