QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#225168 | #2898. Diagonals | PetroTarnavskyi | WA | 2ms | 4440kb | C++17 | 3.0kb | 2023-10-24 02:03:33 | 2023-10-24 02:03:34 |
Judging History
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 N = 8;
map<pair<VI, VI>, tuple<char, VI, VI>> dp[N + 1][N + 2];
map<VI, VI> normDP;
VI norm(VI a)
{
if (normDP.count(a))
return normDP[a];
VI b(SZ(a), -1);
int c = 0;
FOR(i, 0, SZ(a))
{
if (b[i] != -1)
continue;
FOR(j, i, SZ(a))
if (a[i] == a[j])
b[j] = c;
c++;
}
return normDP[a] = b;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(15);
int n;
cin >> n;
vector<string> v(n + 1);
FOR (i, 0, n + 1)
cin >> v[i];
VI initComp(n + 2), initCnt(n + 2, -1);
iota(ALL(initComp), 0);
if (v[1][0] != '+')
initCnt[0] = v[1][0] - '0';
FOR(i, 0, n + 1)
if (v[0][i] != '+')
initCnt[i + 1] = v[0][i] - '0';
dp[0][0][{initComp, initCnt}] = {' ', {}, {}};
VI curComp, curCnt;
FOR(i, 0, n)
{
FOR(j, 0, n)
{
char ch = v[i + 1][j + 1];
for (const auto& [x, y] : dp[i][j])
{
const auto& [comp, cnt] = x;
if ((cnt[j + 1] == 0 || cnt[j + 1] == -1)
&& (cnt[j] > 0 || cnt[j] == -1)
&& (cnt[j + 2] > 0 || cnt[j + 2] == -1)
&& comp[j] != comp[j + 2])
{
VI ncomp = comp, ncnt = cnt;
FOR(k, 0, n + 2)
{
if (comp[k] == comp[j + 2])
{
ncomp[k] = comp[j];
}
}
ncomp[j + 1] = 47;
if (cnt[j] != -1)
ncnt[j]--;
if (cnt[j + 2] != -1)
ncnt[j + 2]--;
ncnt[j + 1] = ch == '+' ? -1 : ch - '0';
dp[i][j + 1][{norm(ncomp), ncnt}] = {'/', comp, cnt};
}
if ((cnt[j + 1] == 1 || cnt[j + 1] == -1) && ch != '0')
{
VI ncomp = comp, ncnt = cnt;
ncnt[j + 1] = ch == '+' ? -1 : ch - '1';
dp[i][j + 1][{comp, ncnt}] = {'\\', comp, cnt};
}
}
}
for (const auto& [x, y] : dp[i][n])
{
const auto& [comp, cnt] = x;
if (cnt.back() != 0 && cnt.back() != -1)
continue;
if (i == n - 1)
{
curComp = comp;
curCnt = cnt;
break;
}
VI ncomp(n + 2), ncnt(n + 2);
RFOR(k, n + 2, 1)
{
ncomp[k] = comp[k - 1];
ncnt[k] = cnt[k - 1];
}
ncomp[0] = 47;
ncnt[0] = v[i + 2][0] == '+' ? -1 : v[i + 2][0] - '0';
dp[i + 1][0][{norm(ncomp), ncnt}] = {' ', comp, cnt};
}
}
assert(SZ(curComp) == n + 2 && SZ(curCnt) == n + 2);
vector<string> ans(n, string(n, ' '));
RFOR(i, n, 0)
{
RFOR(j, n + 1, 0)
{
auto [c, pcomp, pcnt] = dp[i][j][{curComp, curCnt}];
if (j > 0)
{
assert(c == '\\' || c == '/');
ans[i][j - 1] = c;
}
curComp = pcomp;
curCnt = pcnt;
}
}
FOR(i, 0, n)
cout << ans[i] << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 4440kb
input:
8 +11+111++ 1++++1++0 1++2++3++ +1+2+1+3+ +213+++++ 12+232+++ 222+++22+ +++3+3+++ +211+121+
output:
//////// /\\/\//\ /\\///\\ //\/\//\ ///////\ ////\\\\ \\\/\/// /\\\\\/\
result:
wrong answer 8th lines differ - expected: '\///\\//', found: '/\\\\\/\'