QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #850825 | #8355. T3 | HuTao# | Compile Error | / | / | C++14 | 11.3kb | 2025-01-10 12:05:18 | 2025-01-10 12:05:18 |
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)
{
a[i][j] = dd;
q[hh = tt = 0] = {i, j};
int px = -1, py = -1;
while(hh <= tt)
{
int i = q[hh].first, j = q[hh].second, p;
hh ++ ;
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 == 0)
{
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[p][j].first)
{
path[p][j] = {i, j};
q[ ++ tt] = {p, j};
}
}
p = nxr[i][j];
if(p == 0)
{
if(d == 'R' && x == i)
{
px = i, py = j;
break;
}
}
else
{
if(!path[p][j].first)
{
path[p][j] = {i, j};
q[ ++ tt] = {p, j};
}
}
}
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';
}
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;
for(i = 1; i <= tot; i ++ )
{
int x = p[i].first, y = p[i].second;
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;
}#include <bits/stdc++.h>
using namespace std;
const int N = 305, M = N * N;
int n;
int u[N], d[N], l[N], r[N];
int p[N];
string ans[M];
int tot;
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]);
for(int i = 1; i <= n; i ++ )
if(u[i] + d[i] > n || l[i] + r[i] > n)
return puts("NO"), 0;
for(int i = 1; i <= n; i ++ )
{
int cnt = n - l[i] - r[i];
for(int j = 1; j <= n; j ++ ) p[j] = j;
sort(p + 1, p + n + 1, [](const int i, const int j) {return u[i] > u[j];});
int t0 = tot;
for(int t = 1; t <= n && cnt; t ++ )
{
int j = p[t];
if(u[j]) u[j] -- , cnt -- , ans[ ++ tot] = "U" + to_string(j);
}
for(int j = 1; j <= l[i]; j ++ ) ans[ ++ tot] = "L" + to_string(i);
for(int j = 1; j <= r[i]; j ++ ) ans[ ++ tot] = "R" + to_string(i);
// printf("#%d %d\n", i, tot);
if(tot - t0 != n)
{
puts("NO");
return 0;
}
}
for(int i = 1; i <= tot; i ++ ) printf("%s\n", ans[i].c_str());
return 0;
}
詳細信息
answer.code:379:2: error: stray ‘#’ in program
379 | }#include <bits/stdc++.h>
| ^
answer.code:379:3: error: ‘include’ does not name a type
379 | }#include <bits/stdc++.h>
| ^~~~~~~
answer.code:383:11: error: redefinition of ‘const int N’
383 | const int N = 305, M = N * N;
| ^
answer.code:5:11: note: ‘const int N’ previously defined here
5 | const int N = 305;
| ^
answer.code:385:5: error: redefinition of ‘int n’
385 | int n;
| ^
answer.code:7:5: note: ‘int n’ previously declared here
7 | int n;
| ^
answer.code:386:5: error: redefinition of ‘int u [305]’
386 | int u[N], d[N], l[N], r[N];
| ^
answer.code:8:5: note: ‘int u [305]’ previously declared here
8 | int u[N], d[N], l[N], r[N];
| ^
answer.code:386:11: error: redefinition of ‘int d [305]’
386 | int u[N], d[N], l[N], r[N];
| ^
answer.code:8:11: note: ‘int d [305]’ previously declared here
8 | int u[N], d[N], l[N], r[N];
| ^
answer.code:386:17: error: redefinition of ‘int l [305]’
386 | int u[N], d[N], l[N], r[N];
| ^
answer.code:8:17: note: ‘int l [305]’ previously declared here
8 | int u[N], d[N], l[N], r[N];
| ^
answer.code:386:23: error: redefinition of ‘int r [305]’
386 | int u[N], d[N], l[N], r[N];
| ^
answer.code:8:23: note: ‘int r [305]’ previously declared here
8 | int u[N], d[N], l[N], r[N];
| ^
answer.code:387:5: error: conflicting declaration ‘int p [305]’
387 | int p[N];
| ^
answer.code:79:16: note: previous declaration as ‘std::pair<int, int> p [93025]’
79 | pair<int, int> p[N * N];
| ^
answer.code:388:8: error: conflicting declaration ‘std::string ans [93025]’
388 | string ans[M];
| ^~~
answer.code:221:8: note: previous declaration as ‘std::string ans [305]’
221 | string ans[N];
| ^~~
answer.code:389:5: error: redefinition of ‘int tot’
389 | int tot;
| ^~~
answer.code:78:16: note: ‘int tot’ previously declared here
78 | int vis[N][N], tot;
| ^~~
answer.code:391:5: error: redefinition of ‘int main()’
391 | int main()
| ^~~~
answer.code:246:5: note: ‘int main()’ previously defined here
246 | int main()
| ^~~~
answer.code: In function ‘int main()’:
answer.code:406:46: error: no match for ‘operator=’ (operand types are ‘std::pair<int, int>’ and ‘int’)
406 | for(int j = 1; j <= n; j ++ ) p[j] = j;
| ^
In file included from /usr/include/c++/13/bits/stl_algobase.h:64,
from /usr/include/c++/13/algorithm:60,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
from answer.code:1:
/usr/include/c++/13/bits/stl_pair.h:752:9: note: candidate: ‘template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, const _U1&>, std::is_assignable<_T2&, const _U2&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(const std::pair<_U1, _U2>&) [with _U2 = _U1; _T1 = int; _T2 = int]’
752 | operator=(const pair<_U1, _U2>& __p)
| ^~~~~~~~
/usr/include/c++/13/bits/stl_pair.h:752:9: note: template argument deduction/substitution failed:
answer.code:406:46: note: mismatched types ‘const std::pair<_T1, _T2>’ and ‘int’
406 | for(int j = 1; j <= n; j ++ ) p[j] = j;
| ^
/usr/include/c++/13/bits/stl_pair.h:763:9: note: candidate: ‘template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, _U1&&>, std::is_assignable<_T2&, _U2&&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(std::pair<_U1, _U2>&&) [with _U2 = _U1; _T1 = int; _T2 = int]’
763 | operator=(pair<_U1, _U2>&& __p)
| ^~~~~~~~
/usr/include/c++/13/bits/stl_pair.h:763:9: note: template argument deduction/substitution failed:
answer.code:406:46: note: mismatched types ‘std::pair<_T1, _T2>’ and ‘int’
406 | for(int j = 1; j <= n; j ++ ) p[j] = j;
| ^
/usr/include/c++/13/bits/stl_pair.h:727:7: note: candidate: ‘std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(std::__conditional_t<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch&>) [with _T1 = int; _T2 = int; std::__conditional_t<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch&> = const std::pair<int, int>&]’
727 | operator=(__conditional_t<__and_<is_copy_assignable<_T1>,
| ^~~~~~~~
/usr/include/c++/13/bits/stl_pair.h:729:65: note: no known conversion for argument 1 from ‘int’ to ‘std::__conditional_t<true, const std::...