QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#225168#2898. DiagonalsPetroTarnavskyiWA 2ms4440kbC++173.0kb2023-10-24 02:03:332023-10-24 02:03:34

Judging History

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

  • [2023-10-24 02:03:34]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:4440kb
  • [2023-10-24 02:03:33]
  • 提交

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: '/\\\\\/\'