[USACO 2009 Ope S]Cow Line

* Line 1: A single integer: S
* Lines 2..S+1: Line i+1 contains specification i in one of four formats:
* A L -- a cow arrives on the Left of the line
* A R -- a cow arrives on the Right of the line
* D L K -- K cows depart the Left side of the line
* D R K -- K cows depart the Right side of the line

C++14(g++5.4) 解法, 执行用时: 22ms, 内存消耗: 1624K, 提交时间: 2019-08-13 08:43:51

#include <cstdio>

#define N 100010

int s,opt,cnt,q[N],hd(N>>1),tl((N>>1)+1);
char a,b;

int main()
{
	scanf("%d",&s);
	while(s--)
	{
		scanf("\n%c %c",&a,&b);
		if(a=='D')
		{
			scanf("%d",&opt);
			if(b=='L')
				hd+=opt;
			else
				tl-=opt;
		}
		else
		{
			if(b=='L')
				q[hd--]=++cnt;
			else
				q[tl++]=++cnt;
		}
	}
	for(int i(hd+1);i<tl;++i)
		printf("%d\n",q[i]);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 40ms, 内存消耗: 1504K, 提交时间: 2019-08-04 12:04:11

#include<bits/stdc++.h>
using namespace std;
int f[200010];
int main(){
	int l=100000,r=99999,n,tot=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		char t,t2;
		cin>>t>>t2;
		if(t=='A'){
			if(t2=='L')f[--l]=++tot;
			else f[++r]=++tot;
		}
		else if(t=='D'){
			int b;
			cin>>b;
			if(t2=='L')l+=b;
			else r-=b;
		}
	}
	for(int i=l;i<=r;i++)
	cout<<f[i]<<"\n";
	return 0;
}

Python3(3.9) 解法, 执行用时: 202ms, 内存消耗: 7476K, 提交时间: 2021-05-04 01:50:14

from collections import deque
dq=deque()
k=1
for i in range(int(input())):
	a=input().split()
	if a[0]=='A':
		if a[1]=='L':
			dq.appendleft(k)
		else:
			dq.append(k)
		k+=1
	else:
		num=int(a[2])
		if a[1]=='L':
			for i in range(num):
				dq.popleft()
		else:
			for i in range(num):
				dq.pop()
for i in dq:
	print(i)

pypy3(pypy3.6.1) 解法, 执行用时: 733ms, 内存消耗: 26992K, 提交时间: 2021-05-04 01:49:28

cow=[]
k=1
for i in range(int(input())):
	a=input().split()
	if a[0]=='A':
		if a[1]=='L':
			cow.insert(0,k)
		else:
			cow.append(k)
		k+=1
	else:
		num=int(a[2])
		if a[1]=='L':
			for i in range(num):
				cow.pop(0)
		else:
			for i in range(num):
				cow.pop()
for i in cow:
    print(i)

详情