题目

P10711

实际得分

35分。

使用方法

使用手写双向链表。

问题描述

多个点TLE,运行时间都在1.20s，没有WA。
编号：#28，#39，#41，#42，#43，#44，#45。 分布：Subtask #3-#6

问题程序

#include<iostream>
using namespace std;
#define ll long long
const int N = 200010;

struct list{
	int s;//人数 
	bool w; //能否拆分 
	int pre,next;//前后指针 
};

struct sc{
	int name;
	ll s;
};

int q;
int option;
int idx,last=0;
list queue[N];
sc a[N];

void join(int s,bool w){
	queue[++idx].s = s,queue[idx].w = w;
	queue[idx].pre = last;
	queue[idx].next = queue[last].next;
	if(queue[last].next!=-1)
		queue[queue[last].next].pre = idx;
	queue[last].next = idx;
	last  = idx;
}

void leave(int a){
	queue[queue[a].pre].next = queue[a].next;
	if(queue[a].next!=-1){
		queue[queue[a].next].pre = queue[a].pre;
	}else{
		last = queue[a].pre;	
	}
}

void board(ll b){
	int k = 0;
	int it = queue[0].next;
	while(it!=-1 && b>0){
		if(b>=queue[it].s){
			a[++k] = {it,queue[it].s};
			b-=queue[it].s;
			leave(it);
		}else if(queue[it].w){
			a[++k] = {it,b};
			queue[it].s-=b;
			b=0;
		}
		it = queue[it].next;
	}
	cout<<k<<'\n';
	for(int i= 1;i<=k;i++){
		cout<<a[i].name<<' '<<a[i].s<<'\n';
	}
		
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	queue[0].next = -1;
	cin>>q;
	while(q--){
		cin>>option;
		if(option == 1){
			int s;
			bool w;
			cin>>s>>w;
			join(s,w);
		}else if(option==2){
			int a;
			cin>>a;
			leave(a);
		}else{
			ll b;
			cin>>b;
			board(b);
		}
	}
	return 0;
}