提出 #47412428

---

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
	vector a(2, vector<ll>(0));
	vector l(2, vector<ll>(0));
	vector<ll> sm(2);

	// 入力
	for (int num=0; num<2; num++){
		int m; cin >> m;
		a[num].resize(m);
		l[num].resize(m);
		for (int i=0; i<m; i++){
			cin >> a[num][i] >> l[num][i];
			sm[num] += l[num][i];
		}
		reverse(a[num].begin(), a[num].end());
		reverse(l[num].begin(), l[num].end());
	}

	// 0埋め
	if (sm[0] < sm[1]){
		a[0].push_back(0);
		l[0].push_back(sm[1] - sm[0]);
	}
	
	if (sm[0] > sm[1]){
		a[1].push_back(0);
		l[1].push_back(sm[0] - sm[1]);
	}

	// 区間の長さの代わりに累積和（何桁目で数字が変わるか）を使う
	for (int num=0; num<2; num++){
		for (int i=0; i<(int)l[num].size()-1; i++){
			l[num][i+1] += l[num][i];	
		}
	}

	// 足し算の処理
	int p0 = 0, p1 = 0;
	ll now = 0;
	vector<ll> ansa;
	vector<ll> ansl;
	ll val0 = a[0][0], val1 = a[1][0];
	bool carry = 0;
	ll nxt0 = l[0][0], nxt1 = l[1][0]; 
	while (p0 < (int)l[0].size() || p1 < (int)l[1].size()){
		bool something_new = 0; // 位の数字が変化したか？
		if (now == 0) something_new = 1;
		// A の位の数字が変化した場合
		if (p0 < (int)l[0].size() && now >= l[0][p0]){
			p0++;
			if (p0 < (int)l[0].size()){
				nxt0 = l[0][p0];
				val0 = a[0][p0];
			}else{
				break;
			}
			something_new = 1;
		}
		// B の位の数字が変化した場合
		if (p1 < (int)l[1].size() && now >= l[1][p1]){
			p1++;
			if (p1 < (int)l[1].size()){
				nxt1 = l[1][p1];
				val1 = a[1][p1];
			}else{
				break;
			}
			something_new = 1;
		}

		// 足し算
		ll t;
		if (carry){
			t = val0 + val1 + 1;
		}else{
			t = val0 + val1;
		}

		if (t >= 10){
			carry = true;
		}else{
			carry = false;
		}
		
		if (something_new){
			// 桁の数字が変化した場合
			ansa.push_back(t % 10);
			ansl.push_back(1);
			now++;
		}else{
			// 区間をまとめて処理
			ansa.push_back(t % 10);
			ansl.push_back(min(nxt0, nxt1) - now);
			now = min(nxt0, nxt1);
		}
	}

	// 最上位が繰り上がりだった場合
	if (carry){
		ansa.push_back(1);
		ansl.push_back(1);
	}

	// 答えの生成 (ランレングス圧縮)
	vector<ll> reta;
	vector<ll> retl;
	for (int i=0; i<(int)ansa.size(); i++){
		assert (ansl[i] > 0);
		reta.push_back(ansa[i]);
		retl.push_back(ansl[i]);
		if ((int)reta.size() >= 2 && reta[(int)reta.size() - 1] == reta[(int)reta.size() - 2]){
			reta.pop_back();
			retl[(int)retl.size() - 2] += retl[(int)retl.size() - 1];
			retl.pop_back();
		}
	}

	reverse(reta.begin(), reta.end());
	reverse(retl.begin(), retl.end());

	// 出力
	int m = reta.size();
	cout << m << '\n';
	for (int i=0; i<m; i++){
		cout << reta[i] << ' ' << retl[i] << '\n';
	}
}

提出情報

ジャッジ結果