记录编号 187574 评测结果 AAAAAAAAAA
题目名称 [NOI 2003]文本编辑器 最终得分 100
用户昵称 Gravatar张灵犀不和我一般见识真可怕呢(笑 是否通过 通过
代码语言 C++ 运行时间 2.687 s
提交时间 2015-09-19 16:01:09 内存使用 0.31 MiB
显示代码纯文本
#include<cstdio>
#include<iostream>
#include<list>
#include<deque>
#include<cstring>
#include<cmath>
using namespace std;
const int SIZEB=3010;
int M;
class miku//块状链表
{
public:
	int n;
	char a[SIZEB];
	miku(){n=0;}
	void print()
	{
		cout<<n<<endl;
		for(int i=0;i<n;i++)
			printf("%c",a[i]);
		cout<<endl;
	}
};
list<miku> Q;
typedef list<miku>::iterator LBIND;
typedef pair<LBIND,int> BLIND;
BLIND key;
int pos=0;//光标在第几个字符
int totchar=0;//当前有多少个字符
void prin(BLIND x)
{
	cout<<"first:";
	miku a=*x.first;
	a.print();
	cout<<endl;
	cout<<"second:"<<x.second<<endl;
	cout<<endl;
}
void check_Q()
{
	for(LBIND it=Q.begin();it!=Q.end();it++)
	{
		miku a=*it;
		a.print();
	}
}
void initalize()//插入一个空的表
{
	miku tem;
	Q.push_front(tem);
	key.first=Q.begin();key.second=0;
	pos=0;
}
void Move(int k)//将光标移动到k个字符之后
{
	key.first=Q.begin();
	key.second=0;
	while(k>key.first->n) {k-=key.first->n,key.first++;}
	key.second=k;
}
void merge(LBIND key1,LBIND key2)
{
	if(key1->n+key2->n>SIZEB) return;
	memcpy(key1->a+key1->n,key2->a,key2->n);
	key1->n+=key2->n;
	Q.erase(key2);
}
void split(LBIND key1,int k)
{
	miku temp;
	temp.n=key1->n-k;
	memcpy(temp.a,key1->a+k,key1->n-k);
	key1->n=k;
	Q.insert(++key1,temp);
}
void Insert(int k)
{
	if(k==0) return;
	//if(k==1) prin(key);
	split(key.first,key.second);
	//prin(key);
	miku temp;
	totchar+=k;
	char ch;
	int best=sqrt(totchar+0.0);
	LBIND now=key.first;
	for(int i=1;i<=k;i++)
	{
		scanf("%c",&ch);
		while(ch=='\n'||ch=='\r') scanf("%c",&ch);
	//	if(ch=='_') prin(key);
		temp.a[temp.n++]=ch;
		if(temp.n==best)
		{
			now=Q.insert(++now,temp);
			temp.n=0;
		}
		//miku a=*now;
		//if(ch=='_') check_Q();
		//if(ch=='_')cout<<temp.n<<" "<<temp.a[0]<<endl;
	}
	if(temp.n) Q.insert(++now,temp);
	//check_Q();
}
void Delete(int k)
{
	if(k==0) return;
	totchar-=k;
	BLIND key1,key2;
	key1=key;key2=key;
	split(key1.first,key1.second);
	while(key2.first->n-key2.second<k) 
	{
		k-=key2.first->n-key2.second;
		key2.second=0;
		key2.first++;
	}
	key2.second+=k;
	split(key2.first,key2.second);
	Q.erase(++key1.first,++key2.first);
}
void get(int k)
{
	BLIND key1=key;
	//cout<<k<<endl;
	//prin(key1);
	while(key1.first->n-key1.second<k)
	{
		for(int i=key1.second;i<key1.first->n;i++)
		{
			printf("%c",key1.first->a[i]);
		}
		k-=key1.first->n-key1.second;
		key1.second=0;
		key1.first++;
	}
	if(k)
	{
		for(int i=key1.second;i<key1.second+k;i++)
			printf("%c",key1.first->a[i]);
	}
	printf("\n");
}
void Next()
{
	pos++;
	key.second++;
	if(key.second>key.first->n)
	{
		key.second=1;
		key.first++;
	}
}
void Prev()
{
	pos--;
	key.second--;
	if(key.second<0)
	{
		key.first--;
		key.second=key.first->n-1;
	}
}
void keep()
{
	int best=sqrt(totchar+0.1);
	for(LBIND it=Q.begin();it!=Q.end();it++)
	{
		
		while(it!=Q.end()&&!Q.empty()&&it->n==0) it=Q.erase(it);
		if(it==Q.end()) break;
		if(it->n>2*best) split(it,best);
		else
		{
			LBIND key2=it;key2++;
			if(key2==Q.end()) continue;
			if(it->n+key2->n<=best) merge(it,key2);
		}
	}
	if(Q.empty()) initalize();
}
int main()
{
	freopen("editor2003.in","r",stdin);
	freopen("editor2003.out","w",stdout);
	scanf("%d",&M);
	initalize();
	int p;
	string r;
	for(int i=1;i<=M;i++)
	{
		cin>>r;
		//cout<<r<<endl;
		if(r=="Move"||r=="Delete"||r=="Insert"||r=="Get") scanf("%d",&p);
		if(r=="Move") {pos=p;Move(p);}
		else if(r=="Insert") Insert(p);
		else if(r=="Delete") Delete(p);
		else if(r=="Get") get(p);
		else if(r=="Next") Next();
		else if(r=="Prev") Prev();
		else cout<<"error"<<endl;
		if(r=="Insert"||r=="Delete")
		{
			//check_Q();
			//cout<<pos<<endl;
			keep();
			//cout<<"arrive2"<<endl;
			Move(pos);
			//cout<<"***************"<<endl;
		}
	}
	return 0;
}