QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#513400#8813. Records in Chichén ItzáPetroTarnavskyi#RE 0ms0kbC++202.8kb2024-08-10 17:46:082024-08-10 17:46:11

Judging History

你现在查看的是最新测评结果

  • [2024-08-10 17:46:11]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-08-10 17:46:08]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int B = 10;

template<typename T>
void updMin(T& a, T b)
{
	a = min(a, b);
}

template<typename T>
void updMax(T& a, T b)
{
	a = max(a, b);
}

struct Big
{
	VI vec;
	Big (int x)
	{
		vec = {x};
	}
	Big(const string& s)
	{
		vec.resize(SZ(s));
		FOR(i, 0, SZ(s))
			vec[i] = s[i] - '0';
		reverse(ALL(vec));
	}
	bool operator<(const Big& a)
	{
		if (SZ(vec) != SZ(a.vec))
			return SZ(vec) < SZ(a.vec);
		return vec < a.vec;
	}
	void operator+= (const Big& a)
	{
		if (SZ(vec) < SZ(a.vec))
			vec.resize(SZ(a.vec));
		FOR(i, 0, SZ(a.vec))
			vec[i] += a.vec[i];
		for (int i = 0; i < SZ(a.vec) || vec[i] >= B; i++)
		{
			if (vec[i] >= B)
			{
				vec[i] -= B;
				if (i + 1 >= SZ(vec))
					vec.PB(0);
				vec[i + 1]++;
			}
		}
	}
	void print() const
	{
		RFOR(i, SZ(vec), 0)
			cout << vec[i];
		cout << "\n";
	}
};


int n;
vector<string> s(2);

pair<Big, vector<string>> f(int x1, int x2)
{
	vector<string> res(2, string(2 * n, '0'));
	int mnX = min(x1, x2), mxX = max(x1, x2);
	FOR(i, 0, n)
	{
		int j = -1;
		if (i <= mnX)
			j = 0;
		else if (i > mxX)
			j = 1;
		if (j == -1)
			continue;
		bool can2Up = (s[0][2 * i + j] != '1' && s[1][2 * i + j] != '2');
		s[0][2 * i + j] = can2Up ? '2' : '1';
		s[1][2 * i + j] = can2Up ? '1' : '2';
	}
	char digits[2];
	digits[0] = x2 < x1 ? '1' : '2';
	digits[1] = '1' ^ '2' ^ digits[0];
	FOR(i, mnX + 1, mxX + 1)
	{
		FOR(j, 0, 2)
		{
			if (s[0][2 * i + j] == '?' && s[1][2 * i + j] == '?')
				res[0][2 * i + j] = digits[j];
		}
	}
	Big sum(0);
	string cur;
	FOR(i, 0, 2 * n)
	{
		if (s[0][i] == '?')
		{
			sum += cur;
			cur = "";
		}
		else
			cur += s[0][i];
	}
	sum += cur;
	return {sum, res};
}

void solve()
{
	cin >> n;
	FOR(i, 0, 2)
		cin >> s[i];
	int l[2] = {-1, -1}, r[2] = {n, n};
	FOR(i, 0, 2)
	{
		FOR(j, 0, 2 * n)
		{
			if (s[i][j] != '?')
			{
				int d = s[i][j] - '1';
				if (j % 2 == 0)
					updMax(l[d], j / 2);
				else
					updMin(r[d], j / 2);
			}
		}
	}
	if (l[0] >= r[0] || l[1] >= r[1])
	{
		cout << "impossible\n";
		return;
	}
	auto [sum1, res1] = f(l[0], r[1] - 1);
	auto [sum2, res2] = f(r[0] - 1, l[1]);
	if (sum2 < sum1)
	{
		sum1 = sum2;
		res1 = res2;
	}
	sum1.print();
	FOR(i, 0, 2)
		cout << res1[i] << "\n";
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while (t--)
		solve();
	return 0;
}


詳細信息

Test #1:

score: 0
Runtime Error

input:

3
6
1 1 1 1 3 3
5
1 1 2 2 2
10
1 1 1 1 2 2 2 2 3 3

output:


result: