QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#513400 | #8813. Records in Chichén Itzá | PetroTarnavskyi# | RE | 0ms | 0kb | C++20 | 2.8kb | 2024-08-10 17:46:08 | 2024-08-10 17:46:11 |
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