QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#225172 | #2898. Diagonals | PetroTarnavskyi | AC ✓ | 25ms | 16480kb | C++17 | 3.0kb | 2023-10-24 02:24:04 | 2023-10-24 02:24:04 |
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 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)
{
bool ok = true;
for (int c : cnt)
ok &= c == 0 || c == -1;
if (!ok)
continue;
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: 100
Accepted
time: 2ms
memory: 4468kb
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:
ok 8 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 4268kb
input:
8 ++++++11+ +13+13++1 ++21+21++ +11+2222+ +2++3++21 +11+1+2+1 +++322+1+ 11+1+1+11 +1++1++++
output:
/\/\\/// \\\\//\/ /\\////\ \\/////\ //\/\//\ \//////\ /\/\\\// //\\\/\/
result:
ok 8 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 4448kb
input:
8 ++1+++2++ 12++23++2 0222322++ +3+11+3+1 ++++++++1 +213+2++0 +1+3++22+ 2++22+4++ +1+++1+++
output:
\\\\\/\\ \\\\\\\/ ////\\\/ /\\///\/ /\\//\\/ /\///\/\ ///\/\/\ \\/\//\\
result:
ok 8 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 3900kb
input:
5 +1+2++ 1++11+ +3+2++ 02+++1 ++3+1+ +1+++1
output:
\\/\\ \/\\/ \\\\\ ////\ //\\\
result:
ok 5 lines
Test #5:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
5 +++21+ 11+2++ 1++2++ ++32+1 +3++3+ ++0+++
output:
\\/\\ \//\/ \\/\/ \//\/ //\\\
result:
ok 5 lines
Test #6:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
5 ++1+++ 12+++1 +2121+ +2+22+ +323++ ++++1+
output:
////\ ////\ \\/// \\/// /\/\\
result:
ok 5 lines
Test #7:
score: 0
Accepted
time: 5ms
memory: 7904kb
input:
8 +++++++++ ++4+++22+ +3+++3+3+ ++++2+3++ ++1++++21 ++21++3++ +2+++++21 +4+1+2+11 ++++2+1+0
output:
\\//\\\/ \/\\\\\/ //\\/\// //\\//// \//\\\// \/////// \//\/\// /\\\/\\/
result:
ok 8 lines
Test #8:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
1 01 10
output:
/
result:
ok single line: '/'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
1 0+ ++
output:
/
result:
ok single line: '/'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
1 10 01
output:
\
result:
ok single line: '\'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
1 1+ ++
output:
\
result:
ok single line: '\'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
1 +0 ++
output:
\
result:
ok single line: '\'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
1 +1 ++
output:
/
result:
ok single line: '/'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
1 ++ 0+
output:
\
result:
ok single line: '\'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
1 ++ 1+
output:
/
result:
ok single line: '/'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
1 ++ +0
output:
/
result:
ok single line: '/'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
1 ++ +1
output:
\
result:
ok single line: '\'
Test #18:
score: 0
Accepted
time: 3ms
memory: 5292kb
input:
8 +++++++++ +1+2+32+1 ++32++4++ +2+4++++1 +3+++++11 ++21++3+0 +2++23+++ ++1++++1+ +110+0+10
output:
/\\/\\// \\\//\// \/\///\/ \//\\/// ///\\\\/ \\\\\/\\ //\////\ ///\/\//
result:
ok 8 lines
Test #19:
score: 0
Accepted
time: 5ms
memory: 6744kb
input:
8 +++++++++ +3+2+2+20 +2+4+3+++ ++1++2++1 +3++2+++1 +++21+2+2 ++2++24++ +2+3++++1 +2+112+2+
output:
\/\/\/// \\\/\/\\ ///\\\\\ \\//\\/\ /\//\\/\ //\\\\// \/\///\/ \/\\\/\/
result:
ok 8 lines
Test #20:
score: 0
Accepted
time: 3ms
memory: 5016kb
input:
7 ++++++++ +23131+1 +11+1+2+ ++2++1+1 +3++3+++ ++22222+ +3+3222+ ++2+1+2+
output:
/////\/ //\/\\/ \////\/ \//\/// \\\\\\/ \\\\\\/ /\/\\\/
result:
ok 7 lines
Test #21:
score: 0
Accepted
time: 2ms
memory: 4840kb
input:
7 ++++++++ +21221+0 +++1+3++ +3+2++21 +233++2+ +++++2+1 +21+2++1 +++12+2+
output:
/////\/ \\////\ \/\//\\ \\\//\\ //\\/// //\\/// \\\\/\/
result:
ok 7 lines
Test #22:
score: 0
Accepted
time: 5ms
memory: 6068kb
input:
8 +++++++++ +2+233+21 +24++2+21 ++++++1+1 +3++21+22 +23+++3++ +++3+++11 +21++21+0 +1110++1+
output:
\\\\\/\\ \\//\\\\ //\///\\ \////\\\ \\\\\\// //\///// //\\//\/ ////\\\\
result:
ok 8 lines
Test #23:
score: 0
Accepted
time: 2ms
memory: 4416kb
input:
8 +++++++++ +11+1+4+0 ++2++3+++ +131+++1+ ++1+3+320 +2+2+11++ +23+1+2++ +31++1++1 +0+112+0+
output:
//\/\\// \//\\/\\ ///\///\ \/\\//// //////\\ ////\//\ //\////\ /\\\\//\
result:
ok 8 lines
Test #24:
score: 0
Accepted
time: 2ms
memory: 4584kb
input:
7 ++++++++ +24++1+1 ++++2+3+ ++23+231 +3++2+++ +33+121+ ++++++2+ ++0+11+1
output:
\\///\/ //\/\\/ \\\/\\\ \/////\ \\////\ /\\\/// //\\\\\
result:
ok 7 lines
Test #25:
score: 0
Accepted
time: 4ms
memory: 5468kb
input:
7 ++++++++ +232+2+1 +++2++3+ +322+2++ ++24+1+2 ++++++2+ +2++2+4+ +0+10+++
output:
\\\//\/ //\//\/ \\\//\\ /\\//\\ ///\\\/ /\//\\/ /\//\/\
result:
ok 7 lines
Test #26:
score: 0
Accepted
time: 0ms
memory: 5528kb
input:
8 +++++++++ ++3+3+3++ +3+3+3+3+ ++3+++3++ +3+++++2+ ++3+++32+ +3+3+3+31 ++3+2+3++ +++++++++
output:
\\\\\\// \/\/\/// \\\\\\/\ \/\\/\\\ \\\/\\\\ \/\\\/\\ ///\///\ //\\//\\
result:
ok 8 lines
Test #27:
score: 0
Accepted
time: 0ms
memory: 3920kb
input:
3 ++++ +1+1 +31+ +0+0
output:
/\/ /// /\/
result:
ok 3 lines
Test #28:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
4 +++++ +3++2 ++3++ +3+3+ ++2+0
output:
\//\ \\// \\\/ /\//
result:
ok 4 lines
Test #29:
score: 0
Accepted
time: 2ms
memory: 4684kb
input:
7 ++++++++ +3+3+3++ ++3++23+ +3+++321 ++3+++3+ +3+++3++ ++3+3+3+ +++1++++
output:
\\\/\// /\//\\/ ///\\\\ /\///\\ ///\//\ /\/\/\\ //////\
result:
ok 7 lines
Test #30:
score: 0
Accepted
time: 8ms
memory: 7620kb
input:
8 +++++++++ +3+24+++2 ++4+++2++ +++++21+1 +3+3++2++ ++3+2++2+ +++3+++3+ ++++3+3+2 +2+2+2+2+
output:
\\\\//\\ /\//\/\/ //\///\/ \\\///// /\\\\\\/ //\//\\/ \/\\\\\\ \/\/\/\/
result:
ok 8 lines
Test #31:
score: 0
Accepted
time: 13ms
memory: 10896kb
input:
8 +++++++++ +22+2+2+1 +32+2+2+1 ++2+2+1+2 ++2+3++2+ +22++2+3+ ++3++22+1 +3+3+++3+ ++2+110++
output:
\\/\//\\ \\/\//\\ /\/\//\\ \\/\/\\/ \\/\\\\/ \\////// \\\/\\\/ /\////\\
result:
ok 8 lines
Test #32:
score: 0
Accepted
time: 4ms
memory: 5656kb
input:
8 +++++++++ +33++3+3+ +++++33++ ++3+++++1 +3+3+++2+ ++3+1+32+ +++2+3+31 +1+++23++ +11+1+1++
output:
\\//\/// /\\\\\/\ \\///\\\ \\\//\\\ /\//\\// /\\\\\\\ /\///\/\ /////\\\
result:
ok 8 lines
Test #33:
score: 0
Accepted
time: 6ms
memory: 7036kb
input:
8 +++++++++ +33++23+0 ++++2++1+ ++3++3+30 +3+22+2++ ++3++22++ +3++++3+0 +3+223+2+ ++++++2+0
output:
\\//\\// /\\////\ \\/\\\// \////\/\ \\\\\\/\ \/\\\\// \\\\\\\\ /\///\//
result:
ok 8 lines
Test #34:
score: 0
Accepted
time: 3ms
memory: 6956kb
input:
8 +++++++++ ++3++2+20 +3+3+1+++ ++2+3+++2 +++++3+++ +2+2++3++ +1+1+3++1 ++3++33++ +1+1++++0
output:
\\///\// \\\\/\\\ /\/\//\\ /\/\\/// /\/\\\// /\/\\/// \\//\\// /////\\/
result:
ok 8 lines
Test #35:
score: 0
Accepted
time: 5ms
memory: 6312kb
input:
8 +++++++++ +3+1+1+22 ++22222++ +2+++++22 ++2+2+2++ +++2+3++2 +2++2+2++ +4+++3+22 +++11++++
output:
\//\/\\\ //////// \\\\\\\\ //////// \\\\\//\ \/////// \//\\\\\ /\///\//
result:
ok 8 lines
Test #36:
score: 0
Accepted
time: 25ms
memory: 16480kb
input:
8 +++++++++ +2+2+2+2+ +2+2+2+2+ +2+2+2+2+ +2+2+2+2+ +2+2+2+2+ +2+2+2+2+ +2+2+2+2+ +0+0+0+0+
output:
/\/\/\/\ /\/\/\/\ /\/\/\/\ /\/\/\/\ /\/\/\/\ /\/\/\/\ /\/\/\/\ /\/\/\/\
result:
ok 8 lines
Test #37:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
8 +0+0+0+0+ +2+2+2+2+ +2+2+2+2+ +2+2+2+2+ +2+2+2+2+ +2+2+2+2+ +2+2+2+2+ +2+2+2+2+ +++++++++
output:
\/\/\/\/ \/\/\/\/ \/\/\/\/ \/\/\/\/ \/\/\/\/ \/\/\/\/ \/\/\/\/ \/\/\/\/
result:
ok 8 lines
Test #38:
score: 0
Accepted
time: 3ms
memory: 5420kb
input:
8 +++++++++ +22222220 +++++++++ +22222220 +++++++++ +22222220 +++++++++ +22222220 +++++++++
output:
//////// \\\\\\\\ //////// \\\\\\\\ //////// \\\\\\\\ //////// \\\\\\\\
result:
ok 8 lines
Test #39:
score: 0
Accepted
time: 2ms
memory: 4552kb
input:
8 +++++++++ 02222222+ +++++++++ 02222222+ +++++++++ 02222222+ +++++++++ 02222222+ +++++++++
output:
\\\\\\\\ //////// \\\\\\\\ //////// \\\\\\\\ //////// \\\\\\\\ ////////
result:
ok 8 lines