## 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

ajmer
New poster
Posts: 7
Joined: Thu Mar 07, 2013 2:16 am

### Re: 11995 - I Can Guess the Data Structure!

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
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

### Re: 11995 - I Can Guess the Data Structure!

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

### Re: 11995 - I Can Guess the Data Structure!

input

Code: Select all

``````1
2 1``````
ac output

Code: Select all

``impossible``
Check input and AC output for thousands of problems on uDebug!

Katniss
New poster
Posts: 2
Joined: Tue Jul 16, 2013 1:22 am

### 11995 - I Can Guess the Data Structure!

i tried it on every sample , but it gves me WA help!!
Last edited by Katniss on Tue Jul 16, 2013 4:11 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!

It looks like you figured it out.
Check input and AC output for thousands of problems on uDebug!

Katniss
New poster
Posts: 2
Joined: Tue Jul 16, 2013 1:22 am

### Re: 11995 - I Can Guess the Data Structure!

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

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!

According to your uhunt you got AC, and you removed your code.
Check input and AC output for thousands of problems on uDebug!

himu_D_evil
New poster
Posts: 2
Joined: Tue Oct 29, 2013 10:48 pm

### Re: 11995 - I Can Guess the Data Structure!

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

### Re: 11995 - I Can Guess the Data Structure!

Input:

Code: Select all

``````1
1 1``````
Output should be not sure
Check input and AC output for thousands of problems on uDebug!

Kenpachi24
New poster
Posts: 20
Joined: Wed Oct 30, 2013 7:06 pm

### Re: 11995 - I Can Guess the Data Structure!

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

### Re: 11995 - I Can Guess the Data Structure!

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

himu_D_evil
New poster
Posts: 2
Joined: Tue Oct 29, 2013 10:48 pm

### Re: 11995 - I Can Guess the Data Structure!

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

### Re: 11995 - I Can Guess the Data Structure!

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.
Check input and AC output for thousands of problems on uDebug!

priorm
New poster
Posts: 4
Joined: Tue Nov 05, 2013 11:28 am

### Re: 11995 - I Can Guess the Data Structure!

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!
Last edited by priorm on Thu Dec 05, 2013 9:19 am, 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!

Try using a StringTokenizer instead of split()
Check input and AC output for thousands of problems on uDebug!