3059454_ac_281ms_1320k.cc

北大大牛代码 1240道题的原代码 超级权威

#include "stdio.h"
#include "malloc.h"
#define size 1100000
typedef struct node{
	int p;
	int k;
	struct node * pre;
	struct node * next;
}NODE;
NODE * head, * tail;
char mark[ size ];

int main(){
	int cmd;
	int k, p;
	NODE * tmp, * ptr;

	head = tail = NULL;

	for ( p = 0; p < size ; p++ ) mark[ p ] = 0;

	while ( scanf("%d", &cmd) == 1 && cmd ){
		if( cmd == 2 ){
			if ( head == NULL ){
				printf("0\n");
			}else {
				printf("%d\n", tail -> k );
				if ( head == tail ){
					head = tail = NULL;
					continue;
				}
				tmp = tail;
				tail = tail -> pre;
				tmp -> pre -> next = tmp -> next;
				tmp -> next -> pre = tmp -> pre;
				free( tmp );
			}
		} else if ( cmd == 3 ){
				if ( head == NULL ){
					printf("0\n");
				} else {
					printf("%d\n", head -> k );
					if ( head == tail ){
						head = tail = NULL;
						continue;
					}
					tmp = head;
					head = head -> next;
					tmp -> pre -> next = tmp -> next;
					tmp -> next -> pre = tmp -> pre;
					free( tmp );
				}
		} else {
			scanf("%d %d", &k, &p );
			tmp = ( NODE * )malloc( sizeof( NODE ) );
			tmp -> k = k;
			tmp -> p = p;
			if ( head == NULL ){
				head = tail = tmp;
				continue;
			}
			ptr = head;
			if ( p > tail -> p ){
				tmp -> pre = tail;
				tmp -> next = head;
				head -> pre = tmp;
				tail -> next = tmp;
				tail = tmp;
				continue;
			} else if ( p <= head -> p ){
				tmp -> pre = tail;
				tmp -> next = head;
				head -> pre = tmp;
				tail -> next = tmp;
				head = tmp;
				continue;
			}
			while ( ptr != tail ){
				if ( p <= ptr -> p ){
					break;
				}
				ptr = ptr -> next;
			}
			tmp -> next = ptr;
			tmp -> pre = ptr -> pre;
			ptr -> pre -> next = tmp;
			ptr -> pre = tmp;
		}
	}
	return 0;
}