- #include#include#define init_size 1000 typedef struct {
- int head,
- tail,
- size,
- __size,
- *seq;
- }
- Queue;
- typedef Queue * Q_P;
- void init(Q_P q) {
- q - >head = q - >tail = 0;
- q - >__size = init_size;
- q - >size = 0;
- q - >seq = (int * ) malloc(init_size * sizeof(Queue));
- }
- void push(Q_P q, int ele) {
- if (q - >tail + 1 >= q - >__size) {
- q - >seq = (int * ) realloc(q - >seq, sizeof(int) * (q - >__size *= 2));
- }
- q - >seq[q - >tail++] = ele;
- q - >size++;
- //debug
- // printf("PUSH %d SIZE:%d\n",q->seq[q->tail-1],q->size);
- }
- int empty(Q_P q) {
- if (q - >head == q - >tail) return 1;
- return 0;
- }
- void pop(Q_P q) {
- if (!empty(q)) q - >head++,
- q - >size--;
- // printf("POP SIZE:%d\n",q->size);
- }
- int front(Q_P q) {
- if (!empty(q)) return q - >seq[q - >head];
- }
- void print(Q_P q) {
- printf("%d", front(q));
- pop(q);
- while (q - >size != 0) {
- printf(" %d", front(q));
- pop(q);
- }
- printf("\n");
- }
- void test() {
- int i;
- Q_P q = (Q_P) malloc(sizeof(Queue));
- init(q);
- for (i = 0; i < 10; ++i) {
- push(q, i);
- }
- print(q);
- }
- void solve() {
- int n,
- i,
- T;
- scanf("%d", &T);
- while (T--) {
- scanf("%d", &n);
- Q_P a = (Q_P) malloc(sizeof(Queue)),
- b = (Q_P) malloc(sizeof(Queue)); //或者Queue *a,*b;
- init(a);
- init(b);
- for (i = 1; i <= n; ++i) {
- push(a, i);
- push(b, i);
- }
- // print(a);print(b);
- //print the Queue ,but at the same time the action does clear the queue
- if (a - >size != 0 && a - >size <= 3) print(a);
- int cnt = 0;
- while (a - >size > 3 || b - >size > 3) {
- int k;
- for (k = 2; k <= 3; ++k) {
- cnt++;
- if (cnt & 1) {
- while (b - >size != 0) pop(b);
- int cc = 0;
- while (a - >size != 0) {
- if (++cc % k != 0) push(b, front(a));
- pop(a);
- }
- } else {
- while (a - >size != 0) pop(a);
- int cc = 0;
- while (b - >size != 0) {
- if (++cc % k != 0) push(a, front(b));
- pop(b);
- }
- }
- if (a - >size != 0 && a - >size <= 3) {
- print(a);
- break;
- }
- if (b - >size != 0 && b - >size <= 3) {
- print(b);
- break;
- }
- }
- }
- }
- }
- int main() {
- // test();
- solve();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-1967796.html