11995 - I Can Guess the Data Structure!

All about problems in Volume 119. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11995 - I Can Guess the Data Structure!

Post by brianfry713 » Wed May 21, 2014 8:31 pm

Try using BufferedWriter.
Check input and AC output for thousands of problems on uDebug!

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 11995 - I Can Guess the Data Structure!

Post by uDebug » Fri May 23, 2014 1:30 pm

brianfry713,
Thanks for all the great test cases.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Faithkeeper_Rangwan
New poster
Posts: 12
Joined: Sun Jul 07, 2013 7:32 pm

Re: 11995 - I Can Guess the Data Structure!

Post by Faithkeeper_Rangwan » Thu Jun 12, 2014 6:14 pm

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

Code: Select all

Code removed after AC
Last edited by Faithkeeper_Rangwan on Sun Jun 15, 2014 1:59 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11995 - I Can Guess the Data Structure!

Post by brianfry713 » Thu Jun 12, 2014 7:50 pm

I solved this by simulating a standard int queue, priority_queue, and stack. Why are you using deques and vectors instead?
Check input and AC output for thousands of problems on uDebug!

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 11995 - I Can Guess the Data Structure!

Post by lbv » Thu Jun 12, 2014 10:07 pm

Faithkeeper_Rangwan wrote: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
New poster
Posts: 12
Joined: Sun Jul 07, 2013 7:32 pm

Re: 11995 - I Can Guess the Data Structure!

Post by Faithkeeper_Rangwan » Sun Jun 15, 2014 2:02 pm

brianfry713 wrote: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
New poster
Posts: 22
Joined: Tue Oct 29, 2013 6:46 pm

Re: 11995 - I Can Guess the Data Structure! WA plzz help me

Post by cse dipto » Thu Jun 19, 2014 8:04 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11995 - I Can Guess the Data Structure!

Post by brianfry713 » Thu Jun 19, 2014 11:13 pm

Change line 131 to:
else if(s + q + pq > 1)
Check input and AC output for thousands of problems on uDebug!

cse dipto
New poster
Posts: 22
Joined: Tue Oct 29, 2013 6:46 pm

Re: 11995 - I Can Guess the Data Structure!

Post by cse dipto » Thu Jun 19, 2014 11:21 pm

THNKS @brianfry713 thnks a lot thnks again :D

Bad Boy
New poster
Posts: 4
Joined: Fri Jul 13, 2007 5:17 am
Location: CSE, DU(13th)

Re: 11995 - I Can Guess the Data Structure!

Post by Bad Boy » Thu Jul 17, 2014 10:29 am

WA :(
Last edited by Bad Boy on Fri Jul 18, 2014 7:03 am, edited 1 time in total.

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 11995 - I Can Guess the Data Structure!

Post by lbv » Thu Jul 17, 2014 11:48 am

Bad Boy wrote: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
New poster
Posts: 9
Joined: Mon Aug 13, 2007 7:45 am

Re: 11995 - I Can Guess the Data Structure!

Post by pfiesteria » Fri Jul 18, 2014 3:10 am

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
New poster
Posts: 2
Joined: Thu Jan 22, 2015 12:07 pm

Re: 11995 - I Can Guess the Data Structure!

Post by anjan.anoup » Thu Jan 22, 2015 12:17 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11995 - I Can Guess the Data Structure!

Post by brianfry713 » Sat Jan 24, 2015 7:29 am

I solved this by simulating a standard int queue, priority_queue, and stack.
Use the C++ STL.
Check input and AC output for thousands of problems on uDebug!

reza_cse08
New poster
Posts: 8
Joined: Sun Nov 17, 2013 9:55 pm

Re: 11995 - I Can Guess the Data Structure!

Post by reza_cse08 » Thu Apr 16, 2015 8:40 pm

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;
}

Post Reply

Return to “Volume 119 (11900-11999)”