QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#225172#2898. DiagonalsPetroTarnavskyiAC ✓25ms16480kbC++173.0kb2023-10-24 02:24:042023-10-24 02:24:04

Judging History

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

  • [2023-10-24 02:24:04]
  • 评测
  • 测评结果:AC
  • 用时:25ms
  • 内存:16480kb
  • [2023-10-24 02:24:04]
  • 提交

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