11995 - I Can Guess the Data Structure!

[ajmer]

Altought only one test case gave incorrect output, it made me realise quite a few errors in code, so thanks for that. Got AC now.

[raj]

why wrong answer please help me anyone...

Code: Select all

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String [] args)throws IOException{
        BufferedReader k = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter z = new PrintWriter(System.out);
        String line;
        while((line = k.readLine()) != null)
        {
            Queue<Integer> q = new LinkedList<Integer>();
            Stack<Integer> s = new Stack<Integer>();
            PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
            LinkedList<Integer> ans = new LinkedList<Integer>();
            int temp = Integer.valueOf(line);
            int a = 0,b = 0,c = 0;
            while(temp-->0)
            {
                StringTokenizer ss = new StringTokenizer(k.readLine());
                int cheq = Integer.valueOf(ss.nextToken());
                int x = Integer.valueOf(ss.nextToken());
                if(cheq==1)
                {
                    if(a==0)
                    {
                        s.push(x);
                    }
                    if(b==0)
                    {
                        q.add(x);
                    }
                    if(c==0)
                    {
                        pq.add(x);
                    }
                }
                else
                {
                    if(s.size()>=1)
                    {
                        if(s.pop()!=x)
                        {
                            a = 1;
                        }
                    }
                    if(q.size()>=1)
                    {
                        if(q.poll()!=x)
                        {
                            b = 1;
                        }
                    }
                    while(pq.size()!=0)
                    {
                        ans.addFirst(pq.poll());
                    }
                    if(ans.size()>=1)
                    {
                        if(ans.poll()!=x)
                        {
                            c = 1;
                        }
                    }
                    while(ans.size()!=0)
                    {
                        pq.add(ans.poll());
                    }
                }
            }
            if((a==0 && b==0 && c==0)||(a==0 && b==0)||(b==0 && c==0)||(c==0 && a==0))
            {
                z.println("not sure");
            }
            else if(a==0)
            {
                z.println("stack");
            }
            else if(b==0)
            {
                z.println("queue");
            }
            else if(c==0)
            {
                z.println("priority queue");
            }
            else
            {
                z.println("impossible");
            }
        }
        z.flush();
    }
}
 

[brianfry713]

input

Code: Select all

1
2 1

ac output

Code: Select all

impossible

[Katniss]

i tried it on every sample , but it gves me WA help!!

[brianfry713]

It looks like you figured it out.

[Katniss]

it looks like it , but still getting WA!!!

[brianfry713]

According to your uhunt you got AC, and you removed your code.

[himu_D_evil]

why WA??

Code: Select all

#include <bits/stdc++.h>
using namespace std;
#define sc scanf
#define pf printf
long long int read_int();

int main()
{
    int t;
    while(sc("%d", &t)!=EOF)
    {

        stack<int> st;
        queue<int> qu;
        priority_queue<int> pq;
        int sf=1,qf=1,pf=1,f1=0,f2=0;
        vector<int> v1;
        vector<int> v2;
        int a, b;
        int stt,qut,pqt;
        for(int i=0;i<t;i++)
        {
            a=read_int();
            b=read_int();
            if(a==1){
                st.push(b);
                qu.push(b);
                pq.push(b);
                f1=1;
            }

            if(a==2){

                    if(sf && !st.empty()){
                        stt=st.top();
                        st.pop();
                        if(stt!=b){
                                sf=0;
                            }
                        f2=1;
                    }

                    if(qf && !qu.empty()){
                            qut=qu.front();
                            qu.pop();
                            if(qut!=b){
                                qf=0;
                        }
                      f2=1;
                    }

                    if(pf && !pq.empty()){
                            pqt=pq.top();
                            pq.pop();
                        if(pqt!=b){
                            pf=0;
                    }
                  f2=1;
                }
            }
    }
            if(sf+qf+pf > 1 && f1 && f2 ) puts("not sure");
            else if(sf+qf+pf==1 && f1 && f2){
                if(sf==1) puts("stack");
                if(qf==1) puts("queue");
                if(pf==1) puts("priority queue");
                }
            else puts("impossible");

    }
    return 0;

}




long long int read_int(){
	char r;
	bool start=false,neg=false;
	long long int ret=0;
	while(true){
		r=getchar();
		if((r-'0'<0 || r-'0'>9) && r!='-' && !start){
			continue;
		}
		if((r-'0'<0 || r-'0'>9) && r!='-' && start){
			break;
		}
		if(start)ret*=10;
		start=true;
		if(r=='-')neg=true;
		else ret+=r-'0';
	}
	if(!neg)
		return ret;
	else
		return -ret;
}

[brianfry713]

Input:

Code: Select all

1
1 1

Output should be not sure

[Kenpachi24]

Que puedo hacer, para no Obtener Time Limit

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;

/**
*
* @author OSCAR
*/
public class Main {
public static void main(String[] args) throws IOException {
Stack<Integer> pila=new Stack<Integer>();
Queue<Integer> cola = new LinkedList<Integer>();
PriorityQueue<Integer> colap = new PriorityQueue<Integer>(1001, Collections.reverseOrder());

InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String cadena, linea, cad[]=new String[3];
int arreglopila[]=new int[1001], original[]=new int[1001], arreglocola[]=new int[1001], arreglocolap[]=new int[100], banderas[]=new int[5];

while ((cadena=br.readLine())!=null){
int numero=Integer.parseInt(cadena), opcion, valor, contador=0;
banderas[0]=0;
banderas[1]=0;
banderas[2]=0;
for (int i=0; i<numero; i++){
linea=br.readLine();
cad=linea.split(" ");
opcion=Integer.parseInt(cad[0]);
valor=Integer.parseInt(cad[1]);
if (opcion==1){
pila.push(valor);
cola.add(valor);
colap.add(valor);
}
else{
original[contador]=valor;
arreglopila[contador]=pila.pop();
arreglocola[contador]=cola.poll();
arreglocolap[contador]=colap.poll();
if (valor==arreglopila[contador]&& banderas[0]==0)
banderas[0]=0;
else
banderas[0]=1;

if (valor==arreglocola[contador]&& banderas[1]==0)
banderas[1]=0;
else
banderas[1]=1;

if (valor==arreglocolap[contador]&& banderas[2]==0)
banderas[2]=0;
else
banderas[2]=1;

contador++;
}
}
int contador2=0;
for (int i=0; i<3; i++){
if (banderas==0)
contador2++;
}
if (contador2==0)
System.out.println("impossible");
else{
if (contador2>1)
System.out.println("not sure");
else{
if (banderas[0]==0)
System.out.println("stack");
if (banderas[1]==0)
System.out.println("queue");
if (banderas[2]==0)
System.out.println("priority queue");
}
}
}
}
}

[brianfry713]

Try using BufferedWriter

[himu_D_evil]

why wa this time??

Code: Select all

#include <bits/stdc++.h>
using namespace std;
#define sc scanf
#define pf printf
long long int read_int();

int main()
{
        int t;
        while(sc("%d", &t)!=EOF)
        {

            stack<int> st;
            queue<int> qu;
            priority_queue<int> pq;
            int sf=1,qf=1,pf=1,f1=0,f2=0,x=0,y=0,z=0, c1=0, c2=0;
            map<int,int> mp1, mp2;
            int em=0;
            int a, b;
            int stt,qut,pqt;
            for(int i=0;i<t;i++)
            {
                a=read_int();
                b=read_int();
                if(a==1){
                    st.push(b);
                    qu.push(b);
                    pq.push(b);
                    mp1[b]++;
                    f1=1;
                    c1++;
                }

                if(a==2){
                   c2++;
                   if(!mp1[b]) em=1;
                        if(sf && !st.empty()){
                            stt=st.top();
                            st.pop();
                            if(stt!=b){
                                    sf=0;
                                }
                            if(sf){
                                f2=1;
                                x=1;
                            }
                        }

                        if(qf && !qu.empty()){
                                qut=qu.front();
                                qu.pop();
                                if(qut!=b){
                                    qf=0;
                            }
                          if(qf){
                            f2=1;
                            y=1;
                          }
                        }

                        if(pf && !pq.empty()){
                                pqt=pq.top();
                                pq.pop();
                            if(pqt!=b){
                                pf=0;
                           }
                        if(pf){
                            f2=1;
                            z=1;
                        }
                    }
                }
            }
            //cout<<f1<<" "<<f2<<" "<<x<<" "<<y<<" "<<z<<" ";
               if(em) puts("impossible");
              else if(sf+qf+pf==1 && f1 && f2){
                      if(sf==1) puts("stack");
                      if(qf==1) puts("queue");
                      if(pf==1) puts("priority queue");
                    }
                else {
                    if(sf+qf+pf==0) puts("impossible");
                    else puts("not sure");
                }
        }
        return 0;

}


long long int read_int(){
       char r;
       bool start=false,neg=false;
       long long int ret=0;
       while(true){
          r=getchar();
          if((r-'0'<0 || r-'0'>9) && r!='-' && !start){
             continue;
          }
          if((r-'0'<0 || r-'0'>9) && r!='-' && start){
             break;
          }
          if(start)ret*=10;
          start=true;
          if(r=='-')neg=true;
          else ret+=r-'0';
       }
       if(!neg)
          return ret;
       else
          return -ret;
}

[brianfry713]

Your code is unnecessarily complex. You can just simulate the three data structures. You don't need a map and as many extra variables as you have.

[priorm]

Getting a TLE. Thoughts? I can short circuit if the "impossible" case is reached... but that shouldn't be too big of an optimization.

Accepted.


Wow..... Didn't think that would make that much of a difference...

http://stackoverflow.com/questions/6911 ... ring-split

Thanks Brian!

[brianfry713]

Try using a StringTokenizer instead of split()