QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#851327 | #8355. T3 | HuTao | 11 | 7ms | 41704kb | C++14 | 7.5kb | 2025-01-10 17:45:05 | 2025-01-10 17:45:05 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 605;
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;
struct Point{
int x, y;
Point() {}
Point(int _x, int _y) : x(_x), y(_y) {}
inline void Go(char dir)
{
if(dir == 'U') x -- ;
if(dir == 'D') x ++ ;
if(dir == 'L') y -- ;
if(dir == 'R') y ++ ;
}
inline bool Inside()
{
return 1 <= x && x <= n && 1 <= y && y <= n;
}
};
template<typename T>
struct Array2{
T a[N][N] = {};
inline T* operator [](const int &i) {return a[i];}
inline T& operator [](const Point &i) {return a[i.x][i.y];}
};
Array2<char> a;
Array2<int> pos;
Array2<Point> cur;
Point sta[N * N], sta0[N * N];
int tt, tt0;
inline bool DFS(Point x)
{
sta[ ++ tt] = x;
sta0[ ++ tt0] = x;
pos[x] = tt;
for(Point &y = cur[x]; y.Inside(); y.Go(a[x]))
{
if(a[y] == a[x]) continue;
if(!pos[y])
{
if(DFS(y)) return 1;
}
else if(pos[y] > 0)
{
Point yy = y, y = yy;
char d0 = a[x];
for(int i = tt; i > pos[y]; i -- )
{
a[sta[i]] = a[sta[i - 1]];
cur[sta[i]] = sta[i];
}
a[y] = d0, cur[y] = y;
return 1;
}
}
tt -- ;
pos[x] = -1;
return 0;
}
int vis[N][N], mark[N][N];
pair<int, int> q[N * N];
string ans[N * N];
inline bool Topo()
{
int hh = 1, tt = 0;
memset(vis, 0, sizeof vis);
memset(mark, 0, sizeof mark);
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= n; j ++ )
{
if(!vis[i][j] && a[i][j] == 'U' && (i == 1 || vis[i - 1][j])) q[ ++ tt] = {i, j}, mark[i][j] = 1;
if(!vis[i][j] && a[i][j] == 'D' && (i == n || vis[i + 1][j])) q[ ++ tt] = {i, j}, mark[i][j] = 1;
if(!vis[i][j] && a[i][j] == 'L' && (j == 1 || vis[i][j - 1])) q[ ++ tt] = {i, j}, mark[i][j] = 1;
if(!vis[i][j] && a[i][j] == 'R' && (j == n || vis[i][j + 1])) q[ ++ tt] = {i, j}, mark[i][j] = 1;
}
while(hh <= tt)
{
int i = q[hh].first, j = q[hh].second;
vis[i][j] = 1;
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 ++ ;
// printf("!%d %d\n", i, j);
for(int k = 1; k <= n; k ++ )
if(!vis[k][j])
{
if(a[k][j] == 'U' && !mark[k][j]) q[ ++ tt] = {k, j}, mark[k][j] = 1;
break;
}
for(int k = n; k >= 1; k -- )
if(!vis[k][j])
{
if(a[k][j] == 'D' && !mark[k][j]) q[ ++ tt] = {k, j}, mark[k][j] = 1;
break;
}
for(int k = 1; k <= n; k ++ )
if(!vis[i][k])
{
if(a[i][k] == 'L' && !mark[i][k]) q[ ++ tt] = {i, k}, mark[i][k] = 1;
break;
}
for(int k = n; k >= 1; k -- )
if(!vis[i][k])
{
if(a[i][k] == 'R' && !mark[i][k]) q[ ++ tt] = {i, k}, mark[i][k] = 1;
break;
}
}
// for(int i = 1; i <= n; i ++ )
// {
// for(int j = 1; j <= n; j ++ )
// printf("%d", vis[i][j]);
// puts("");
// }
// exit(0);
return tt == n * n;
}
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';
}
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 ++ ) printf("%s\n", a[i] + 1);
// puts("");
for(int k = 1; k <= n; k ++ )
for(int l = 1; l <= n; l ++ )
cur[k][l] = Point(k, l);
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= n; j ++ )
{
while(DFS(Point(i, j)))
{
for(int i = 1; i <= tt0; i ++ ) pos[sta0[i]] = 0;
tt = tt0 = 0;
}
for(int i = 1; i <= tt0; i ++ ) pos[sta0[i]] = 0;
tt = tt0 = 0;
}
// for(int i = 1; i <= n; i ++ ) printf("%s\n", a[i] + 1);
Topo();
for(int i = 1; i <= n * n; i ++ ) printf("%s\n", ans[i].c_str());
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 11
Accepted
Test #1:
score: 11
Accepted
time: 4ms
memory: 37320kb
input:
1 0 1 0 0
output:
D1
result:
ok OK
Test #2:
score: 11
Accepted
time: 0ms
memory: 41412kb
input:
3 0 0 1 1 1 1 0 1 0 1 2 1
output:
U3 L2 R2 D2 D3 R1 R2 R3 D1
result:
ok OK
Test #3:
score: 11
Accepted
time: 0ms
memory: 37608kb
input:
3 0 0 2 2 0 0 1 0 2 1 1 0
output:
L1 U3 D1 U3 R1 D1 L3 R2 L3
result:
ok OK
Test #4:
score: 11
Accepted
time: 3ms
memory: 39364kb
input:
3 0 0 0 0 1 0 1 0 0 1 3 3
output:
L1 R1 R2 R3 R2 R3 R2 D2 R3
result:
ok OK
Test #5:
score: 11
Accepted
time: 0ms
memory: 37488kb
input:
2 1 0 0 0 0 0 1 2
output:
U1 R1 R2 R2
result:
ok OK
Test #6:
score: 11
Accepted
time: 4ms
memory: 35748kb
input:
3 0 1 0 1 1 0 0 2 2 1 1 0
output:
U2 R1 L2 R2 L3 D2 L2 D1 L3
result:
ok OK
Test #7:
score: 11
Accepted
time: 0ms
memory: 26552kb
input:
2 0 0 2 0 1 0 1 0
output:
NO
result:
ok OK
Test #8:
score: 11
Accepted
time: 0ms
memory: 37376kb
input:
3 0 0 1 0 1 2 1 2 0 0 0 2
output:
L1 U3 L2 D3 L2 D3 R3 D2 R3
result:
ok OK
Test #9:
score: 11
Accepted
time: 4ms
memory: 37612kb
input:
2 1 1 0 0 0 0 2 0
output:
R1 U2 R1 U1
result:
ok OK
Test #10:
score: 11
Accepted
time: 0ms
memory: 41704kb
input:
3 2 0 1 1 1 1 1 1 0 0 0 1
output:
U1 U3 D1 D2 R3 U1 L1 D3 L2
result:
ok OK
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: 39424kb
input:
1 1 0 0 0
output:
U1
result:
ok OK
Test #32:
score: 25
Accepted
time: 0ms
memory: 37320kb
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: 39656kb
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: 25
Accepted
time: 0ms
memory: 39364kb
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 L6 R6 R7 R8 L9 D4 D7 D8 R9 U1 L1 U5 U6 U7 U8 R6 R8 D1 L9 D7 D9 R9 U1 U3 L1 U8 R6 D1 L8 D7 D9 R5 D6 R9 L1 R6 L7 L8 R5 D6 R9 U9 D2 D3 U9 R2 D2 D3 R2 D2 D2 L3 U3 L3 U3 L4 U4 L4 U4 L5 U4 U4 L8 D5 L7 D8 R4 D7 R4 R3 U6 R3 U5
result:
ok OK
Test #35:
score: 25
Accepted
time: 3ms
memory: 39400kb
input:
18 5 5 2 7 4 3 4 2 7 4 5 0 3 4 3 3 7 1 5 6 6 5 2 7 6 6 0 3 4 3 6 3 4 5 3 7 4 4 5 6 2 8 2 3 4 3 4 7 6 6 6 5 1 4 10 5 7 4 5 6 7 4 6 2 4 3 5 3 8 2 7 6
output:
U1 U3 U11 U17 R1 L2 L3 L6 R6 R9 L12 R12 R13 R14 L15 R15 L16 R16 L17 R17 L18 D7 D8 D10 D11 D12 D14 D16 D17 R18 L1 U17 U18 R1 L2 U1 L6 L12 R12 R13 R14 L15 R15 R17 D1 L18 D7 D8 D10 D11 D12 D14 D16 D18 R18 L1 U17 U16 R1 U2 L2 U1 L6 R12 R13 R14 L15 R15 D17 D1 L18 D7 D10 D11 D12 D14 D18 R11 D15 R18 U4 L1 ...
result:
ok OK
Test #36:
score: 25
Accepted
time: 4ms
memory: 39360kb
input:
29 7 7 6 10 6 6 5 10 8 10 10 7 5 9 5 4 7 7 12 7 12 7 8 6 6 7 7 10 5 4 6 4 8 6 11 5 7 8 6 9 6 6 10 11 4 5 6 6 8 6 7 11 8 8 6 7 11 7 8 8 10 12 9 7 10 6 9 8 6 5 11 10 8 7 9 3 8 5 8 5 8 7 4 6 8 6 6 8 10 6 7 5 10 6 8 5 8 8 8 7 10 6 4 5 6 8 8 7 4 4 5 7 7 8 10 6
output:
L1 U2 U7 U9 U11 U13 U19 U20 U21 U22 U23 U24 U25 U28 R1 R2 L3 R3 L4 R4 L5 R5 L6 L7 L8 L9 L10 L11 L12 L13 L14 R14 R19 R20 R21 R22 R23 R24 L25 R25 L26 R26 L27 R27 L28 R28 L29 D8 D10 D11 D12 D14 D15 D16 D17 D18 D19 D20 D21 D23 D24 D25 D26 D28 R29 U1 L1 U7 U9 U19 U21 U23 U28 R1 L4 L5 U29 L6 L7 L8 L14 R14...
result:
ok OK
Test #37:
score: 25
Accepted
time: 4ms
memory: 37324kb
input:
40 9 9 10 8 8 6 9 8 10 4 10 4 7 8 9 11 11 7 7 8 8 7 13 14 14 14 13 9 16 6 12 12 9 17 5 11 4 10 12 15 10 15 13 6 8 16 10 13 11 17 9 14 8 17 4 10 11 11 8 8 9 13 9 9 6 11 9 5 7 16 11 11 12 8 13 12 11 12 5 10 10 7 9 11 11 8 9 16 7 9 7 12 7 10 12 9 14 17 15 8 9 10 6 8 10 11 11 11 13 10 15 8 16 12 9 13 8 ...
output:
U1 U2 U3 U5 U10 U13 U25 U26 U27 U29 U30 U31 U32 U33 U34 U36 U38 U40 L2 L3 L4 L5 L6 L7 L8 R8 R17 R18 R19 L26 R26 L27 L28 R28 L29 L31 L32 R32 L33 R33 L34 R34 L35 R35 L36 R36 L37 R37 L38 R38 L39 R39 L40 D14 D16 D17 D18 D19 D20 D21 D22 D23 D24 D25 D26 D27 D28 D29 D30 D31 D32 D33 D34 D36 D38 R40 U3 L1 U5...
result:
ok OK
Test #38:
score: 25
Accepted
time: 7ms
memory: 39656kb
input:
40 13 12 13 9 14 7 10 11 14 13 13 10 11 11 12 9 10 7 12 8 13 7 6 9 10 12 10 6 5 12 10 8 12 8 12 7 12 9 2 9 9 8 8 9 5 11 11 9 12 11 12 13 11 9 9 14 11 13 11 9 9 13 12 9 6 14 18 9 14 6 13 12 8 10 8 12 6 7 13 9 8 5 12 8 12 11 9 12 6 7 11 8 8 9 11 11 16 6 5 12 10 8 6 6 13 12 14 7 13 8 11 9 10 11 9 9 10 ...
output:
U1 U2 U4 U5 U6 U7 U8 U9 U10 U11 U12 U13 U14 U16 U17 U19 U21 U22 U23 U24 U26 U27 U28 U31 R1 L2 R2 L3 L4 L5 R8 R11 L21 R22 R24 L25 R25 R26 R27 R28 L29 R29 L30 R30 L31 R31 L32 R32 L33 R33 L34 R34 L35 R35 L36 R36 L37 R37 L38 R38 L39 R39 L40 D15 D16 D17 D18 D19 D20 D21 D22 D23 D24 D25 D26 D27 D28 D29 D30...
result:
ok OK
Test #39:
score: 25
Accepted
time: 3ms
memory: 39356kb
input:
17 0 1 2 0 1 0 1 1 0 2 0 1 2 0 0 2 1 0 1 2 2 0 3 1 1 2 0 1 0 0 1 1 2 0 8 7 9 9 4 8 7 9 8 9 7 8 8 5 9 7 12 6 8 6 5 11 9 10 8 7 7 8 8 5 7 7 8 4
output:
L1 U3 U7 R1 L2 R2 L3 R3 L4 R4 L5 R5 L6 R6 L7 R7 L8 R8 L9 R9 L10 R10 L11 R11 L12 R12 L13 R13 L14 L15 R15 L16 R16 L17 D6 R17 L1 R1 L2 R2 L3 R3 L4 R4 L5 R5 L6 R6 L7 R7 L8 R8 L9 R9 L10 R10 L11 L12 U17 L15 R15 L16 R16 L17 D6 R17 L1 R1 L2 R2 L3 R3 R4 L5 R5 L6 R6 L7 R7 L8 R8 L9 R9 L10 U16 R10 L11 U2 L12 L1...
result:
ok OK
Test #40:
score: 25
Accepted
time: 4ms
memory: 39364kb
input:
39 18 21 22 15 21 21 20 15 19 20 19 15 15 23 14 19 21 20 21 18 17 17 17 20 19 16 17 16 20 20 20 20 14 17 15 15 14 18 16 20 13 15 18 12 11 18 16 17 16 16 21 22 13 23 18 16 17 15 18 18 17 19 18 15 21 19 17 16 14 15 16 23 18 19 23 19 17 18 2 4 1 0 2 1 2 3 0 4 4 1 3 1 1 0 2 4 2 2 3 2 3 2 1 4 0 1 6 1 1 1...
output:
U1 U2 U3 U4 U5 U6 U7 U8 U9 U10 U11 U12 U13 U14 U15 U16 U17 U18 U19 U20 U21 U22 U23 U24 U25 U26 U27 U28 U33 U34 U35 U36 U37 U38 U39 R7 R10 R11 R12 L14 D1 D2 D3 D4 D6 D7 D8 D9 D10 D11 D12 D13 D14 D15 D16 D17 D18 D19 D20 D21 D22 D23 D24 D25 D26 D27 D28 D29 D30 D31 D32 D33 D34 D35 D36 D37 D38 D39 U1 U2 ...
result:
ok OK
Test #41:
score: 0
Wrong Answer
time: 3ms
memory: 39656kb
input:
40 17 18 21 17 19 18 18 17 22 14 20 17 18 23 19 18 24 18 20 13 14 14 15 16 23 20 22 19 18 15 19 19 17 21 14 17 21 12 19 24 18 16 16 19 18 16 20 19 15 19 17 15 18 16 17 17 13 16 15 24 22 23 20 21 15 16 11 18 16 21 17 19 18 13 21 18 14 27 18 15 3 6 0 2 3 2 2 2 1 1 1 2 1 2 3 2 1 0 3 1 1 1 1 4 4 3 2 0 3...
output:
U1 U2 U3 U4 U5 U6 U7 U8 U9 U10 U11 U12 U13 U14 U15 U16 U17 U18 U19 U20 U21 U22 U23 U24 U25 U26 U27 U28 U36 U37 U38 U39 U40 R9 L10 L19 L24 L29 L39 D1 D3 D4 D5 D7 D8 D9 D11 D12 D13 D14 D15 D16 D17 D20 D21 D22 D23 D24 D25 D26 D27 D28 D29 D30 D31 D32 D33 D34 D35 D36 D37 D38 D39 D40 U1 U2 U3 U4 U5 U6 U7 ...
result:
wrong output format Unexpected end of file - token expected
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...