11995 - I Can Guess the Data Structure!

[brianfry713]

Try using BufferedWriter.

[uDebug]

brianfry713,
Thanks for all the great test cases.

[Faithkeeper_Rangwan]

Got RTE, don't know where it came from.

Code: Select all

Code removed after AC

[brianfry713]

I solved this by simulating a standard int queue, priority_queue, and stack. Why are you using deques and vectors instead?

[lbv]

Got RTE, don't know where it came from.

Try:

Input

Code: Select all

5
1 10
2 10
2 20
2 30
1 40

Output

Code: Select all

impossible

[Faithkeeper_Rangwan]

I solved this by simulating a standard int queue, priority_queue, and stack. Why are you using deques and vectors instead?

I used vector for queue since I could use it for comparison without popping it out one by one first.

[cse dipto]

Code: Select all

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <cctype>
#include <stack>
#include <queue>
#include <map>
#include <vector>
#include <sstream>
#include <utility>

using namespace std;
stack<int> mys ;
queue<int> myq ;
priority_queue<int>mypq ;

int ot[1000],sot[1000],qot[1000],pqot[1000] ;

int main()
{
    int i,j,k,t_case,n,m,indx1,indx2,indx3,indx4,s,q,pq ;
    while(cin >> t_case)
    {
        indx1 = indx2 = indx3 = indx4 = 0 ;
        s = q = pq = 0 ;
        memset(ot,0,sizeof(ot)) ;
        memset(sot,0,sizeof(sot)) ;
        memset(qot,0,sizeof(qot)) ;
        memset(pqot,0,sizeof(pqot)) ;
        for(i = 1 ; i <= t_case ; i++)
        {
            cin >> n >> m ;
            if(n == 1)
            {
                mys.push(m) ;
                myq.push(m) ;
                mypq.push(m) ;
            }
            if(n == 2)
            {
                ot[indx1++] = m ;
                if(!mys.empty())
                {
                   sot[indx2++] = mys.top() ;
                   mys.pop() ;
                }
                if(!myq.empty())
                {
                   qot[indx3++] = myq.front() ;
                   myq.pop() ;
                }
                if(!mypq.empty())
                {
                    pqot[indx4++] = mypq.top() ;
                    mypq.pop() ;
                }
            }
        }
        while(!mys.empty())
        {
            mys.pop() ;
        }
        while(!myq.empty())
        {
            myq.pop() ;
        }
        while(!mypq.empty())
        {
            mypq.pop() ;
        }
        for(i = 0 ; i < indx1 ; i++)
        {
            if(sot[i] == ot[i])
            {
                s = 1 ;
            }
            else
            {
                s = 0 ;
                break ;
            }
        }
        for(i = 0 ; i < indx1 ; i++)
        {
            if(qot[i] == ot[i])
            {
                q = 1 ;
            }
            else
            {
                    q = 0 ;
                break ;
            }
        }
        for(i = 0 ; i < indx1 ; i++)
        {
            if(pqot[i] == ot[i])
            {
                pq = 1 ;
                }
            else
            {
                pq = 0 ;
                break ;
            }
        }
        if(s == 0 && q == 0 && pq == 0 && indx2 == 0 && indx3 == 0 && indx4 == 0 && indx1 == 0)
        {
            cout << "not sure" << endl ;
        }
        else if(s == 0 && q == 0 && pq == 0 && indx2 == 0 && indx3 == 0 && indx4 == 0 && indx1 > 0)
        {
            cout << "impossible" << endl ;
        }
        else if(s == 1 && q == 0 && pq == 0)
        {
            cout << "stack" << endl ;
        }
        else if(s == 0 && q == 1 && pq == 0)
        {
            cout << "queue" << endl ;
        }
        else if(s == 0 && q == 0 && pq == 1)
        {
            cout << "priority queue" << endl ;
        }
        else if(s == 1 && q == 0 && pq == 1 || s == 0 && q == 1 && pq == 1 || s == 1 && q == 1 && pq == 1)
        {
            cout << "not sure" << endl ;
        }
        else if(s == 0 && q == 0 && pq == 0)
        {
            cout << "impossible" << endl ;
        }
    }
    return 0;
}

[brianfry713]

Change line 131 to:
else if(s + q + pq > 1)

[cse dipto]

THNKS @brianfry713 thnks a lot thnks again

[Bad Boy]

WA

[lbv]

I have got runtime error :-s dont know why, please help me....

Try the test case posted here:
http://acm.uva.es/board/viewtopic.php?f ... 30#p369509

[pfiesteria]

x is not unique.
So
input:

Code: Select all

4
1 1
1 1
2 1
2 1

output:

Code: Select all

not sure

[anjan.anoup]

Hi, I checked with all the Sample TC available here, it gives correct ans. But got WA !! . Help required .

Code: Select all

#include <stdio.h>
#define MAX_VAL 1010
int main()
{
    int i, type, x, tC, qu[MAX_VAL], st[MAX_VAL], pqu[MAX_VAL], first, last, maxval;
    int isQU, isST, isPQU, isIMP;
    while(scanf("%d", &tC) != EOF){
        for(i = 0; i < MAX_VAL; i++)
            pqu[i] = 0;
        first = 0, last = 0, i = 0, maxval = 0, isQU = 1, isST = 1, isPQU = 1, isIMP = 0;
        while(tC--){
            scanf("%d %d", &type, &x);
            if(type == 1){
                qu[i] = x;
                st[i] = x;
                pqu[x] += 1;
                x > maxval ? maxval = x : maxval;
                last = i;
                i += 1;
            }
            else if(type == 2){
                if(!(x == qu[last])){
                    isQU = 0;
                }
                if(!(x == st[first])){
                    isST = 0;
                }
                if(!pqu[x] || (x != maxval)){
                    isPQU = 0;
                }
                if(last > 0)
                    last -= 1;
                else if(last == 0){}
                else
                    isIMP = 1;
                first += 1;
                if(pqu[x] > 0){
                    pqu[x] -= 1;
                    if(pqu[x] == 0){
                        x -= 1;
                        while(x && !pqu[x]){x--;}
                        maxval = x;
                    }
                }
                else{
                    isIMP = 1;
                }
            }
        }
        if(((isQU && isPQU) || ( isPQU && isST) || (isQU && isST)) && !isIMP){
            printf("not sure\n");
        }
        else if(isQU && !isPQU && !isST && !isIMP){
            printf("stack\n");
        }
        else if(isPQU && !isQU && !isST && !isIMP){
            printf("priority queue\n");
        }
        else if(isST && !isQU && !isPQU && !isIMP){
            printf("queue\n");
        }
        else{
            printf("impossible\n");
        }
    }
    return 0;
}

[brianfry713]

I solved this by simulating a standard int queue, priority_queue, and stack.
Use the C++ STL.

[reza_cse08]

I am new at forum. I got wrong answer, but unable to understand why?
Here is my code

Code: Select all

#include<iostream>
#include<cstring>
#include<cstdio>


using namespace std;

int main()
{
    int n=0;

    while(cin>>n && n!=EOF)
    {
       bool pqBool = true;
       int c=0,v=0, q=0,st=0, j=0, k =0, pq =0, aLength=0, sLength=0;
       int a[1000]={0};
       int b[1000]={0};

        for(int s=0;s<n;s++)
        {
            cin>>c>>v;

            if(c==1)
            {
                a[aLength++] = v;
                j++;
                if(pqBool)
                {
                    //s[0]=v;
                    b[sLength++] = v;
                    for(int ss=1;ss<sLength;ss++)
                    {
                        for(int t=ss;t>0 && b[t]<b[t-1];t--)
                        {
                            int temp = b[t-1];
                            b[t-1] = b[t];
                            b[t] = temp;
                        }
                    }
                }
            }
            else
            {
                k++;
                if(v==a[aLength-1])
                    st++;
                if(v==a[q])
                    q++;
                if(pqBool && v==b[sLength-1])
                    {sLength--; pq++;}
                else
                    pqBool=false;

                if(aLength>0)
                    aLength--;
            }
        }
        if(k>0 && j>=k)
        {
            if((k==st && k==q)||(k==st && k==pq)||(k==q && k==pq))
                cout<<"not sure\n";
            else if(k==st && j>=k)
                cout<<"stack\n";
            else if(k==q && j>=k)
                cout<<"queue\n";
            else if(pqBool && n>1)
                cout<<"priority queue\n";
            else
                cout<<"impossible\n";
        }
        else if(k==0 && j>=k)
            cout<<"not sure\n";
        else
            cout<<"impossible\n";
    }

    return 0;
}