# 11607: 【原1607】天真队列

### 题目描述

author: Chika 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1607 ﻿## Description

## Input Format

• `0`: 来了一个新人。如果每一个人都曾经入过一次队列了，你应当忽略这个操作。
• `1`: 队首的人离开了，请输出这个人的编号。如果队列空了，你应当输出"-1"。

## Output Format

``````对于每一个询问类事件，输出对应的答案或者是"-1"。
``````

## Sample Input

``````2
1 2
2
0
1
``````

## Sample Output

``````1
``````

## Limits

• 对于50%的数据，n, q <= 4000
• 对于100%的数据，n, q <= 2000000, 每个人所属的团体id满足0 <= id <= 10^9

## Pangbo13's solution

``````#include<iostream>
#include<queue>
#include<map>
using namespace std;

int x = 0, w = 1;
char ch = 0;
while (ch < '0' || ch > '9') {
if (ch == '-')
w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x  = x * 10 + (ch - '0');
ch = getchar();
}
return x * w;
}
class naive_queue{
map<int,queue<int>> pos;
queue<int> group;
public:
naive_queue(){};
void push(int group_id,int person_id){
auto p = pos.find(group_id);
if(p == pos.end()){
p = pos.insert(pair<int,queue<int>>(group_id,{})).first;
}
queue<int>& q = (*p).second;
if(q.empty()){
group.push(group_id);
}
q.push(person_id);
}
int pop(){
auto q = pos.find(group.front());
int ans = (*q).second.front();
(*q).second.pop();
if((*q).second.empty()){
group.pop();
}
return ans;
}
int front(){
auto q = pos.find(group.front());
return (*q).second.front();
}
bool empty(){
return group.empty();
}
};

int main(){
int* buffer;
naive_queue nq;
int n,q,front = 0,person_id = 1;
buffer = new int[n];
for(int i = 0;i<n;i++){
}
for(int i = 0;i<q;i++){
int choice;
switch(choice){
case 0:
if(front < n){
nq.push(buffer[front],person_id);
++ front;
++ person_id;
}
break;
case 1:
if(nq.empty()){
printf("-1\n");
}else{
printf("%d\n",nq.pop());
}
break;
}
}
delete[] buffer;
}
``````

## q4x3's solution

``````/**
* 全wa了
* 不写了
* 题意理解错了属实拉跨
**/
#include <iostream>
#include <stdio.h>
#define re register

using namespace std;

x = 0;
char ch;
bool f = 0;
while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
if (ch == '-') f = 1;
else x = ch - '0';
while(ch = getchar(), ch >= '0' && ch <= '9') x = 10 * x + ch - '0';
x = f ? -x : x;
}

int p[2000233], n, query, op, idq[2000233], numq[2000233], rear, pnum, head, qcur;
// int p[200], n, query, op, idq[200], numq[200], idnum, pnum, head, qcur;
inline int find(const int &x) {
for(re int i = head;i < rear;++ i) {
if(idq[i] == x) return i;
}
return -1;
}

int main() {
for(re int i = 0;i < n;++ i) {
}
for(int i = 0;i < query;++ i) {
if(!op) {
if(pnum == n) continue;
else {
int tmp = find(p[pnum]);
++ qcur;
if(tmp == -1) {
++ numq[rear];
idq[rear ++] = p[pnum ++];
} else {
++ pnum;
++ numq[tmp];
}
}
} else {
if(qcur) {
-- qcur;
}
} else {
printf("%d\n", -1);
}
}
}
return 0;
}
``````

## satgo1546's solution

``````#include <map>
#include <cstdio>
#include <cstdlib>
using namespace std;

struct node {
int g; // 团体号
int next; // 链式队列中下一个节点的下标
};

int n;
// 通过在数组里链接下标的方式来实现链式队列的同时，避免了new和delete。
node a[2000005];
int tail = -1;
// 下一个要入队的人的下标。
int outer = 0;
// 记录每个团体末尾是谁，a[grouptail[团体号]]就是团体末尾的那个node。
map<int, int> grouptail;

int main(int argc, char *argv[]) {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i].g);
a[i].next = -1;
}
scanf("%d", &argc);
while (argc--) {
int op;
scanf("%d", &op);
if (op) {
// 出队。
puts("-1");
continue;
}
// 输出的“编号”是指此人第几个入队。
}
if (head < 0) tail = -1;
} else {
// 入队。
if (outer >= n) continue;
grouptail[a[outer].g] = outer;
} else {
// 找一团体号相同的组的尾巴。
int ind = tail;
if (grouptail.find(a[outer].g) != grouptail.end()) ind = grouptail[a[outer].g];
a[outer].next = a[ind].next;
a[ind].next = outer;
if (a[outer].next < 0) tail = outer;
grouptail[a[outer].g] = outer;
}
outer++;
}
// 调试用输出。
if (0) {
for (int ind = 0; ind < n; ind++) {
printf("[%2d] %4d %2d ", ind, a[ind].g, a[ind].next);
if (ind == tail) printf(" tail");
if (ind == outer) printf(" outer");
printf("\n");
}