読者です 読者をやめる 読者になる 読者になる

UVa11995 I Can Guess the Data Structure!

解法
各データ構造の実際の pop の出力と、入力の出力とを比較する。
push していないのに pop している入力による impossible に注意。

#include <bits/stdc++.h>

using namespace std;

int main() {
  
  int N;
  while(cin >> N) {
    queue<int> q;
    stack<int> stk;
    priority_queue<int> pq;

    vector<int> vq, vs, vp, vout;

    bool impossible = false;
    for(int i=0; i<N; i++) {
      int op, x;
      cin >> op >> x;
      if(impossible) continue;
      if(op == 1) {
	q.push(x);
	stk.push(x);
	pq.push(x);
      }
      else {
	if(q.empty()) {
	  impossible = true;
	  continue;
	}
	vq.push_back(q.front()); q.pop();
	vs.push_back(stk.top()); stk.pop();
	vp.push_back(pq.top()); pq.pop();
	vout.push_back(x);
      }
    }
    
    int cnt = (vq == vout) + (vs == vout) + (vp == vout);
    if(cnt == 0 || impossible) {
      cout << "impossible\n";
    }
    else if(cnt > 1) {
      cout << "not sure\n";
    }
    else {
      if(vq == vout) { cout << "queue\n"; }
      if(vs == vout) { cout << "stack\n"; }
      if(vp == vout) { cout << "priority queue\n"; }
    }
  }
  
  return 0;
}