読者です 読者をやめる 読者になる 読者になる

JOI 2010 春合宿 day2-1 「a+b problem」

面倒と言わざるを得ない・・・
stackでやりました。

#include<cstdio>
#include<stack>
#define rep(i,n) for(int i = 0; i < n; i++)
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int, ll> P;

stack<P> ans;

void in(int a, ll l){
	if (!l) return;
	if (!ans.empty() && ans.top().fi == a){ l += ans.top().se; ans.pop();}
	
	ans.push(P(a,l));
	return;
}

int main(){
	bool k = false, no[2] = {true,true};
	int m[2], ina, inl, a[2] = {0,0}, na;
	ll l[2] = {0,0}, nl;
	stack<P> x[2];
	
	rep(i,2){
		scanf("%d",&m[i]);
		rep(j,m[i]){
			scanf("%d%d",&ina,&inl);
			x[i].push(P(ina,inl));
		}
	}
	
	while (no[0] || no[1]) {
		rep(i,2){
			if (!l[i]){
				if (x[i].empty()) {
					a[i] = 0;
					l[i] = 1ll<<60;
					no[i] = false;
				} else {
					a[i] = x[i].top().fi;
					l[i] = x[i].top().se;
					x[i].pop();
				}
			}
		}
		
		na = a[0] + a[1]; nl = min(l[0],l[1]);
		
		if (k){
			if (na >= 9) {
				in(na - 9, nl);
				l[0] -= nl; l[1] -= nl;
			} else {
				in(na + 1, 1);
				in(na, nl - 1);
				l[0] -= nl; l[1] -= nl;
				k = false;
			}
		} else {
			if (na <= 9) {
				in(na, nl);
				l[0] -= nl; l[1] -= nl;
			} else {
				in(na - 10, 1);
				in(na - 9, nl - 1);
				l[0] -= nl; l[1] -= nl;
				k = true;
			}
		}
	}
	
	ans.pop();
	printf("%d\n",int(ans.size()));
	while (!ans.empty()) {
		printf("%d %lld\n",ans.top().fi, ans.top().se);
		ans.pop();
	}
}