QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#135468#6394. Turn on the LightUrgantTeam#RE 0ms0kbC++234.2kb2023-08-05 15:53:172023-08-05 15:53:21

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-05 15:53:21]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-08-05 15:53:17]
  • 提交

answer

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define x first
#define y second

using namespace std;

typedef long double ld;
typedef long long ll;

char matr[105][105];
int alive[105][105];
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
int sosx[4] = {-2, 0, 2, 0}, sosy[4] = {0, 2, 0, -2};
vector <int> g[10005];

bool used[10005];
int pairL[10005], pairR[10005];

bool dfs(int v)
{
 	used[v] = true;
 	for (int u : g[v])
 	{
 	 	if (pairR[u] == 0)
 	 	{
 	 	 	pairL[v] = u, pairR[u] = v;
 	 	 	return true;
 	 	}
 	 	if (!used[pairR[u]] && dfs(pairR[u]))
 	 	{
 	 	 	pairL[v] = u, pairR[u] = v;
 	 	 	return true;
 	 	}
 	}
 	return false;
}

int main()
{
 	freopen("input.txt", "r", stdin);
 	freopen("output.txt", "w", stdout);
	ios_base::sync_with_stdio(0); cin.tie(0);

	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= 2 * n - 1; i++)
		for (int j = 1; j <= 2 * m - 1; j++)
			cin >> matr[i][j];

	int quant = 0;
	for (int i = 1; i <= 2 * n - 1; i++)
		for (int j = 1; j <= 2 * m - 1; j++)
		{
		 	if (i % 2 == 1 && j % 2 == 1)
		 	{
		 		int fr = 0;
		 		for (int k = 0; k < 8; k++)
		 		{
		 		 	int nx = i + dx[k], ny = j + dy[k];
		 		 	if (1 <= nx && nx <= 2 * n - 1 && 1 <= ny && ny <= 2 * m - 1) fr++;
		 		}
		 		if (fr == matr[i][j] - '0') continue;
				alive[i][j] = ++quant;
		 	}
		 	else matr[i][j] = '#';
		}

	for (int i = 1; i <= 2 * n - 1; i++)
		for (int j = 1; j <= 2 * m - 1; j++)
		{
		 	if (alive[i][j] != 0)
		 	{
		 		int sos = 0;
		 		for (int k = 0; k < 4; k++)
		 		{
		 		 	int nx = i + sosx[k], ny = j + sosy[k];
		 		 	if (1 <= nx && nx <= 2 * n - 1 && 1 <= ny && ny <= 2 * m - 1) sos++;
		 		}
            	
            	if (sos == 2 || sos == 4)
            	{
            	 	for (int k = 0; k < 4; k++)
            	 	{
                     	int nx = i + sosx[k], ny = j + sosy[k];
		 		 		if (1 <= nx && nx <= 2 * n - 1 && 1 <= ny && ny <= 2 * m - 1 && alive[nx][ny] != 0 && mp(i, j) < mp(nx, ny))
		 		 		{
		 		 			g[alive[i][j]].pb(alive[nx][ny]);
		 		 			g[alive[nx][ny]].pb(alive[i][j]); 	
		 		 		}
                    }
            	}
            	if (sos == 3)
            	{
            	    pair <int, int> rev;
            	    for (int k = 0; k < 4; k++)
            	 	{
                     	int nx = i + sosx[k], ny = j + sosy[k];
		 		 		if (!(1 <= nx && nx <= 2 * n - 1 && 1 <= ny && ny <= 2 * m - 1)) rev = mp(-sosx[k], -sosy[k]);
                    }
                    for (int k = 0; k < 4; k++)
            	 	{
                     	int nx = i + sosx[k], ny = j + sosy[k];
		 		 		if (1 <= nx && nx <= 2 * n - 1 && 1 <= ny && ny <= 2 * m - 1 && alive[nx][ny] != 0 && mp(i, j) < mp(nx, ny) && 
		 		 			mp(sosx[k], sosy[k]) != rev)
		 		 		{
		 		 			g[alive[i][j]].pb(alive[nx][ny]);
		 		 			g[alive[nx][ny]].pb(alive[i][j]); 	
		 		 		}
                    }
            	}
		 	}
		}

	if (quant % 2 == 1) cout << "NO\n", exit(0);

	vector <int> lefts;
	for (int i = 1; i <= 2 * n - 1; i++)
		for (int j = 1; j <= 2 * m - 1; j++)
			if (alive[i][j] != 0 && (i + j) % 4 == 2) lefts.pb(alive[i][j]);
	if ((int) lefts.size() != quant / 2) cout << "NO\n", exit(0);

	bool fl = true;
	int match = 0;
	while (fl)
	{
	 	fl = false;
	 	for (int v : lefts) used[v] = false;
	 	for (int v : lefts)
	 		if (!used[v] && pairL[v] == 0 && dfs(v))
	 		{
	 		 	match++;
	 		 	fl = true;
	 		}
	}
	if (match != (int) lefts.size()) cout << "NO\n", exit(0);

	cout << "YES\n";
	for (int i = 1; i <= 2 * n - 1; i++)
		for (int j = 1; j <= 2 * m - 1; j++)
		{
		 	if (alive[i][j] != 0) continue;
		 	if ((i + j) % 4 != 2) continue;

		 	int sos = pairL[alive[i][j]];
		 	for (int k = 0; k < 4; k++)
     	 	{
              	int nx = i + sosx[k], ny = j + sosy[k];
  		 		if (1 <= nx && nx <= 2 * n - 1 && 1 <= ny && ny <= 2 * m - 1 && alive[nx][ny] == sos)
  		 		{
  		 			matr[i + sosx[k] / 2][j + sosy[k] / 2] = '.'; 	
  		 		}
            }
        }

    for (int i = 1; i <= 2 * n - 1; i++)
    {
     	for (int j = 1; j <= 2 * m - 1; j++)
     		cout << matr[i][j];
     	cout << '\n';
    }
	return 0;
}

詳細信息

Test #1:

score: 0
Dangerous Syscalls

input:

3

output:


result: