QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#72639 | #2563. Curly Racetrack | CSU2023 | WA | 2ms | 3624kb | C++14 | 3.8kb | 2023-01-17 14:17:49 | 2023-01-17 14:17:50 |
Judging History
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'