QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #850892 | #8355. T3 | HuTao# | 0 | 2ms | 14424kb | C++14 | 11.5kb | 2025-01-10 12:43:32 | 2025-01-10 12:43:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 305;
int n;
int u[N], d[N], l[N], r[N];
template<const int N, const int M>
struct Dinic{
int s, t;
int la[N], cur[N], ne[M], en[M], w[M], idx = 1;
int dis[N], q[N], hh, tt;
inline void AddEdge(int a, int b, int c)
{
ne[ ++ idx] = la[a];
la[a] = idx;
en[idx] = b;
w[idx] = c;
}
inline void Add(int a, int b, int c)
{
AddEdge(a, b, c);
AddEdge(b, a, 0);
}
inline bool BFS()
{
memset(dis, -1, sizeof dis);
dis[s] = 0;
q[hh = tt = 0] = s;
while(hh <= tt)
{
int u = q[hh ++ ];
if(u == t) return 1;
cur[u] = la[u];
for(int i = la[u]; i; i = ne[i])
{
int v = en[i];
if(w[i] && dis[v] == -1)
{
dis[v] = dis[u] + 1;
q[ ++ tt] = v;
}
}
}
return 0;
}
inline int DFS(int u, int f)
{
if(u == t || !f) return f;
int res = 0;
for(int &i = cur[u]; i; i = ne[i])
{
int v = en[i];
if(dis[v] == dis[u] + 1 && w[i])
{
int d = DFS(v, min(f, w[i]));
if(!d) dis[v] = -1;
f -= d, res += d;
w[i] -= d, w[i ^ 1] += d;
}
}
return res;
}
inline int MaxFlow()
{
int res = 0;
while(BFS()) res += DFS(s, 1e9);
return res;
}
};
Dinic<N * N + N * 2, 6 * N * N + 4 * N> G;
mt19937 mrand(578196);
char a[N][N], aa[N][N];
int vis[N][N], tot;
pair<int, int> p[N * N];
int nxu[N][N], nxd[N][N], nxl[N][N], nxr[N][N];
inline void Init()
{
for(int i = 1; i <= n; i ++ )
{
int la = 0;
for(int j = 1; j <= n; j ++ )
{
nxu[j][i] = la;
if(a[j][i] == 'U') la = j;
}
}
for(int i = 1; i <= n; i ++ )
{
int la = n + 1;
for(int j = n; j >= 1; j -- )
{
nxd[j][i] = la;
if(a[j][i] == 'D') la = j;
}
}
for(int i = 1; i <= n; i ++ )
{
int la = 0;
for(int j = 1; j <= n; j ++ )
{
nxl[i][j] = la;
if(a[i][j] == 'L') la = j;
}
}
for(int i = 1; i <= n; i ++ )
{
int la = n + 1;
for(int j = n; j >= 1; j -- )
{
nxr[i][j] = la;
if(a[i][j] == 'R') la = j;
}
}
}
pair<int, int> q[N * N], path[N][N];
int hh, tt;
inline bool BFS(int i, int j, char dd, char d, int x)
{
hh = 0, tt = -1;
memset(path, 0, sizeof path);
a[i][j] = dd;
int p;
if(dd == 'U')
{
p = nxu[i][j];
if(p == 0)
{
}
else
{
if(!path[p][j].first)
{
path[p][j] = {i, j};
q[ ++ tt] = {p, j};
}
}
}
if(dd == 'D')
{
p = nxd[i][j];
if(p == n + 1)
{
}
else
{
if(!path[p][j].first)
{
path[p][j] = {i, j};
q[ ++ tt] = {p, j};
}
}
}
if(dd == 'L')
{
p = nxl[i][j];
if(p == 0)
{
}
else
{
if(!path[i][p].first)
{
path[i][p] = {i, j};
q[ ++ tt] = {i, p};
}
}
}
if(dd == 'R')
{
p = nxr[i][j];
if(p == n + 1)
{
}
else
{
if(!path[i][p].first)
{
path[i][p] = {i, j};
q[ ++ tt] = {i, p};
}
}
}
int px = -1, py = -1;
while(hh <= tt)
{
int i = q[hh].first, j = q[hh].second, p;
hh ++ ;
// printf("!%d %d\n", i, j);
p = nxu[i][j];
if(p == 0)
{
if(d == 'U' && x == j)
{
px = i, py = j;
break;
}
}
else
{
if(!path[p][j].first)
{
path[p][j] = {i, j};
q[ ++ tt] = {p, j};
}
}
p = nxd[i][j];
if(p == n + 1)
{
if(d == 'D' && x == j)
{
px = i, py = j;
break;
}
}
else
{
if(!path[p][j].first)
{
path[p][j] = {i, j};
q[ ++ tt] = {p, j};
}
}
p = nxl[i][j];
if(p == 0)
{
if(d == 'L' && x == i)
{
px = i, py = j;
break;
}
}
else
{
if(!path[i][p].first)
{
path[i][p] = {i, j};
q[ ++ tt] = {i, p};
}
}
p = nxr[i][j];
if(p == n + 1)
{
if(d == 'R' && x == i)
{
px = i, py = j;
break;
}
}
else
{
if(!path[i][p].first)
{
path[i][p] = {i, j};
q[ ++ tt] = {i, p};
}
}
}
if(px == -1) return a[i][j] = d, 0;
a[px][py] = d;
do{
int qx = path[px][py].first, qy = path[px][py].second;
if(qx < px) a[qx][qy] = 'U';
if(qx > px) a[qx][qy] = 'D';
if(qy < py) a[qx][qy] = 'L';
if(qy > py) a[qx][qy] = 'R';
px = qx, py = qy;
}while(px != i || py != j);
return 1;
}
string ans[N];
inline void Topo()
{
hh = 1, tt = 0;
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= n; j ++ )
{
if(a[i][j] == 'U' && i == 1) q[ ++ tt] = {i, j};
if(a[i][j] == 'D' && i == n) q[ ++ tt] = {i, j};
if(a[i][j] == 'L' && j == 1) q[ ++ tt] = {i, j};
if(a[i][j] == 'R' && j == n) q[ ++ tt] = {i, j};
}
while(hh <= tt)
{
int i = q[hh].first, j = q[hh].second;
if(a[i][j] == 'U' || a[i][j] == 'D') ans[hh] = a[i][j] + to_string(j);
else ans[hh] = a[i][j] + to_string(i);
hh ++ ;
if(a[i + 1][j] == 'U') q[ ++ tt] = {i + 1, j};
if(a[i - 1][j] == 'D') q[ ++ tt] = {i - 1, j};
if(a[i][j + 1] == 'L') q[ ++ tt] = {i, j + 1};
if(a[i][j - 1] == 'R') q[ ++ tt] = {i, j - 1};
}
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++ ) scanf("%d", &u[i]);
for(int i = 1; i <= n; i ++ ) scanf("%d", &d[i]);
for(int i = 1; i <= n; i ++ ) scanf("%d", &l[i]);
for(int i = 1; i <= n; i ++ ) scanf("%d", &r[i]);
G.s = n * n + n * 2 + 1, G.t = G.s + 1;
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= n; j ++ )
{
G.Add(G.s, (i - 1) * n + j, 1);
G.Add((i - 1) * n + j, j + n * n, 1);
G.Add((i - 1) * n + j, i + n * n + n, 1);
}
for(int i = 1; i <= n; i ++ )
{
G.Add(i + n * n, G.t, u[i] + d[i]);
G.Add(i + n * n + n, G.t, l[i] + r[i]);
}
if(G.MaxFlow() != n * n) return puts("NO"), 0;
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= n; j ++ )
{
if(G.w[((i - 1) * n + j - 1) * 6 + 5]) a[i][j] = 'U';
else a[i][j] = 'L';
}
// n = 3;
// a[1][1] = 'R', a[1][2] = 'D', a[1][3] = 'R', a[1][4] = 0;
// a[2][1] = 'U', a[2][2] = 'D', a[2][3] = 'R', a[2][4] = 0;
// a[3][1] = 'U', a[3][2] = 'L', a[3][3] = 'R', a[3][4] = 0;
for(int T = 1; T <= 1000; T ++ )
{
for(int i = 1; i <= n; i ++ )
{
int cc = 0;
for(int j = 1; j <= n && cc < u[i]; j ++ )
if(a[j][i] == 'U' || a[j][i] == 'D')
{
a[j][i] = 'U';
cc ++ ;
}
cc = 0;
for(int j = n; j >= 1 && cc < d[i]; j -- )
if(a[j][i] == 'U' || a[j][i] == 'D')
{
a[j][i] = 'D';
cc ++ ;
}
cc = 0;
for(int j = 1; j <= n && cc < l[i]; j ++ )
if(a[i][j] == 'L' || a[i][j] == 'R')
{
a[i][j] = 'L';
cc ++ ;
}
cc = 0;
for(int j = n; j >= 1 && cc < r[i]; j -- )
if(a[i][j] == 'L' || a[i][j] == 'R')
{
a[i][j] = 'R';
cc ++ ;
}
}
// for(int i = 1; i <= n; i ++ ) puts(a[i] + 1);
// puts("");
memset(vis, 0, sizeof vis);
int flag = 1;
int ttt = 0;
for(int i = 1; i <= n && flag; i ++ )
for(int j = 1; j <= n && flag; j ++ )
{
int x = i, y = j;
ttt ++ ;
while(!vis[x][y] && x >= 1 && x <= n && y >= 1 && y <= n)
{
vis[x][y] = ttt;
if(a[x][y] == 'U') x -- ;
else if(a[x][y] == 'D') x ++ ;
else if(a[x][y] == 'L') y -- ;
else if(a[x][y] == 'R') y ++ ;
}
if(vis[x][y] == ttt)
{
i = x, j = y, flag = 0;
tot = 0;
do{
p[ ++ tot] = {x, y};
if(a[x][y] == 'U') x -- ;
else if(a[x][y] == 'D') x ++ ;
else if(a[x][y] == 'L') y -- ;
else if(a[x][y] == 'R') y ++ ;
}while(x != i || y != j);
// shuffle(p + 1, p + tot + 1, mrand);
int i;
Init();
for(i = 1; i <= tot; i ++ )
{
int x = p[i].first, y = p[i].second;
// printf("#%d %d\n", x, y);
if(a[x][y] == 'U')
{
if(BFS(x, y, 'L', 'U', y) || BFS(x, y, 'R', 'U', y)) break;
}
if(a[x][y] == 'D')
{
if(BFS(x, y, 'L', 'D', y) || BFS(x, y, 'R', 'D', y)) break;
}
if(a[x][y] == 'L')
{
if(BFS(x, y, 'U', 'L', y) || BFS(x, y, 'D', 'L', y)) break;
}
if(a[x][y] == 'R')
{
if(BFS(x, y, 'U', 'R', y) || BFS(x, y, 'D', 'R', y)) break;
}
}
if(i > tot)
{
puts("NO");
return 0;
}
}
}
if(flag)
{
Topo();
for(int i = 1; i <= n * n; i ++ ) printf("%s\n", ans[i].c_str());
return 0;
}
}
puts("No");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 11
Accepted
time: 2ms
memory: 14424kb
input:
1 0 1 0 0
output:
D1
result:
ok OK
Test #2:
score: 0
Wrong Answer
time: 0ms
memory: 14368kb
input:
3 0 0 1 1 1 1 0 1 0 1 2 1
output:
U3 L2 R2 D2 D3 R1 D1 R2 R3
result:
wrong answer A tile is pushed out of the grid.
Subtask #2:
score: 0
Time Limit Exceeded
Test #11:
score: 0
Time Limit Exceeded
input:
290 28 35 25 29 26 23 36 36 24 39 27 36 24 26 31 28 30 27 25 32 37 26 38 20 31 30 30 35 33 24 25 27 20 26 32 26 33 38 25 29 27 34 25 31 21 22 33 33 24 24 31 31 26 31 25 28 33 27 30 27 24 30 29 26 32 36 20 31 28 23 22 23 37 32 32 27 33 30 27 42 25 31 25 25 26 32 25 35 28 27 33 26 35 39 23 22 26 29 35...
output:
result:
Subtask #3:
score: 0
Time Limit Exceeded
Test #21:
score: 0
Time Limit Exceeded
input:
289 30 29 31 35 25 34 26 28 25 25 44 26 33 30 27 30 33 37 26 27 43 28 28 40 31 36 21 26 35 28 31 29 41 25 30 25 35 28 38 24 26 26 24 24 25 27 18 44 31 24 37 28 26 31 27 32 29 24 24 32 20 35 26 39 30 28 33 30 27 28 37 35 29 22 27 27 31 30 25 31 31 22 30 34 33 31 30 29 41 26 38 36 28 28 21 22 31 34 32...
output:
result:
Subtask #4:
score: 0
Wrong Answer
Test #31:
score: 25
Accepted
time: 0ms
memory: 14372kb
input:
1 1 0 0 0
output:
U1
result:
ok OK
Test #32:
score: 25
Accepted
time: 1ms
memory: 10536kb
input:
2 0 1 0 1 0 0 1 1
output:
U2 D2 R1 R2
result:
ok OK
Test #33:
score: 25
Accepted
time: 0ms
memory: 14060kb
input:
3 0 1 0 0 1 2 2 1 0 0 1 1
output:
L1 L2 R2 D2 D3 L1 D3 R3 U2
result:
ok OK
Test #34:
score: 0
Wrong Answer
time: 0ms
memory: 14296kb
input:
9 2 1 3 4 3 3 2 3 2 2 4 2 1 1 2 4 2 2 4 0 3 3 1 1 2 3 2 0 2 2 2 2 4 1 2 4
output:
L1 U2 U5 U6 U7 U8 L3 L4 R6 R7 R8 L9 D4 D7 D8 R9 L1 U5 U6 U7 U8 L1 U1 D9 R6 R8 D1 L9 R9 D7 R9 U3 L1 R2 U8 U9 U1 D9 R5 R6 D1 L8 D7 D6 R9 U9 L6 D8 R5 R6 L7 L8 L7 D6 D2 R4 D3 D2 D7 R4 D3 D2 R3 U6 D2 L3 R3 R2 U3 L3 U3 L4 U4 L4 U4 L5 U4 U5 U4 L8 D5
result:
wrong answer A tile is pushed out of the grid.
Subtask #5:
score: 0
Time Limit Exceeded
Test #77:
score: 0
Time Limit Exceeded
input:
299 72 66 62 73 80 85 70 93 79 88 77 72 67 70 73 84 77 62 80 77 88 63 69 76 73 91 64 76 75 65 74 71 71 68 81 80 74 77 69 75 73 87 90 82 86 79 76 83 69 72 73 73 75 78 76 80 66 76 67 75 72 71 77 63 80 68 82 63 74 67 74 72 73 76 71 72 66 78 74 65 69 80 76 71 72 74 77 70 85 60 65 89 66 64 77 63 78 82 80...