QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#72639#2563. Curly RacetrackCSU2023WA 2ms3624kbC++143.8kb2023-01-17 14:17:492023-01-17 14:17:50

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-17 14:17:50]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3624kb
  • [2023-01-17 14:17:49]
  • 提交

answer

#include <bits/stdc++.h>

template <class T>
inline void read(T &res)
{
	char ch; bool flag = false; res = 0;
	while (ch = getchar(), !isdigit(ch) && ch != '-');
	ch == '-' ? flag = true : res = ch ^ 48;
	while (ch = getchar(), isdigit(ch))
		res = res * 10 + ch - 48;
	flag ? res = -res : 0;
}

template <class T>
inline void put(T x)
{
	if (x > 9)
		put(x / 10);
	putchar(x % 10 + 48);
}

template <class T>
inline void _put(T x)
{
	if (x < 0)
		x = -x, putchar('-');
	put(x);
}

template <class T>
inline void CkMin(T &x, T y) {x > y ? x = y : 0;}
template <class T>
inline void CkMax(T &x, T y) {x < y ? x = y : 0;}
template <class T>
inline T Min(T x, T y) {return x < y ? x : y;}
template <class T>
inline T Max(T x, T y) {return x > y ? x : y;}
template <class T>
inline T Abs(T x) {return x < 0 ? -x : x;}
template <class T>
inline T Sqr(T x) {return x * x;}
// 若传入 int x 同时结果可能爆 int 应这样写 Sqr((ll)x)

using std::map;
using std::set;
using std::pair;
using std::bitset;
using std::string;
using std::vector;
using std::complex;
using std::multiset;
using std::priority_queue;

typedef long long ll;
typedef long double ld;
typedef complex<ld> com;
typedef pair<int, int> pir;
const ld pi = acos(-1.0);
const ld eps = 1e-8;
const int Maxn = 1e9;
const int Minn = -1e9;
const int mod = 998244353;

const int N = 105;
const int N2 = 1e4 + 5;
int n, m, tis, Tl, Tr, ans;
int mateR[N], lef[N][N], vis[N2];
char s[N][N];

struct arc
{
	int to; 
	arc *nxt;
}*adj[N], p[N2], *P = p;

inline void linkArc(int x, int y)
{
	(++P)->nxt = adj[x]; adj[x] = P; P->to = y;
}

inline bool Hungary(int x)
{
	int y;
	for (arc *e = adj[x]; e; e = e->nxt)
		if (!mateR[y = e->to])
			return mateR[y] = x, true;
	for (arc *e = adj[x]; e; e = e->nxt)
	{
		if (vis[y = e->to] == tis)
			continue ;
		vis[y] = tis;
		if (Hungary(mateR[y]))
			return mateR[y] = x, true;
	}
	return false;
}

inline int maxMatch()
{
	int cnt = 0;
	for (int i = 1; i <= Tl; ++i)
	{
		++tis;
		if (Hungary((i)))
			++cnt;
	}
	return cnt;
}

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i)
		scanf("%s", s[i] + 1);
	for (int i = 1; i <= n; ++i)
	{
		s[i][0] = '1';
		s[i][m + 1] = '3';	
	}
	for (int i = 1; i <= m; ++i)
	{
		s[0][i] = '1';
		s[n + 1][i] = '2';
	}
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			if (s[i][j] != 'x')
				++ans;
	for (int i = 1; i <= n; ++i)
		for (int l = 0, r = 1; l < m + 1; l = r++)
		{	
			while (!isdigit(s[i][r]))
				++r;
			if (!(((r - l - 1 & 1) ^ (s[i][r] <= '2') ^ (s[i][l] <= '2')) & 1))
			{
				bool flago = true, flagx = false;
				for (int j = l + 1; j < r; ++j)
				{
					if (s[i][j] == 'x')
					{
						flagx = true;
						break ;
					}
					if (s[i][j] != 'o')
						flago = false;
				}
				if (!flagx)
				{
					if (flago)
					{
						puts("-1");
						return 0;
					}
					--ans;
					++Tl;
					for (int j = l + 1; j < r; ++j)
						if (s[i][j] != 'o')
							lef[i][j] = Tl;
				}
			}
		}
	for (int j = 1; j <= m; ++j)
		for (int l = 0, r = 1; r < n + 1; l = r++)
		{
			while (!isdigit(s[r][j]))
				++r;
			if (!((r - l - 1 & 1) ^ (s[r][j] - 48 & 1) ^ (s[l][j] - 48 & 1)))
			{
				bool flago = true, flagx = false;
				for (int i = l + 1; i < r; ++i)
				{
					if (s[i][j] == 'x')
					{
						flagx = true;
						break ;
					}
					if (s[i][j] != 'o')
						flago = false;
				}
				if (!flagx)
				{
					if (flago)
					{
						puts("-1");
						return 0;
					}
					--ans;
					++Tr;
					for (int i = l + 1; i < r; ++i)
						if (s[i][j] != 'o')
						{
							if (lef[i][j])
								linkArc(lef[i][j], Tr);
						}
				}
			}	
		}
	put(ans + maxMatch()), putchar('\n');
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3548kb

input:

4 5
4...x
.2..2
.o1x.
3..3o

output:

12

result:

ok 1 number(s): "12"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

2 3
4o2
3x1

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3584kb

input:

100 47
.....4.42..4.2....4242........o242424....o4....
3...3........31...1......2..3...o1313.......13.
.o..........2...14...........2..4........2..2..
..................2....232.......4..13..x.41...
42...1.4....3..3...1.2.32...1...4...424..2...4.
.1.3.2...242...4...4..............23...........
..x.....

output:

-1

result:

wrong answer 1st numbers differ - expected: '4166', found: '-1'