Submission #995058

---

Source Code Expand

#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#include <iostream>

using namespace std;

#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

namespace MF {
#define MAXN 101010
#define MAXM 202020
#define wint int
const wint wEPS = 0;
const wint wINF = 1001001001;
int n, m, ptr[MAXN], next[MAXM], zu[MAXM];
wint capa[MAXM], tof;
int lev[MAXN], see[MAXN], que[MAXN], *qb, *qe;
void init(int _n) {
	n = _n; m = 0; memset(ptr, ~0, n * 4);
}
void ae(int u, int v, wint w0, wint w1 = 0) {
	next[m] = ptr[u]; ptr[u] = m; zu[m] = v; capa[m] = w0; ++m;
	next[m] = ptr[v]; ptr[v] = m; zu[m] = u; capa[m] = w1; ++m;
}
wint augment(int src, int ink, wint flo) {
	if (src == ink) return flo;
	wint f;
	for (int &i = see[src]; ~i; i = next[i]) if (capa[i] > wEPS && lev[src] < lev[zu[i]]) {
		if ((f = augment(zu[i], ink, min(flo, capa[i]))) > wEPS) {
			capa[i] -= f; capa[i ^ 1] += f; return f;
		}
	}
	return 0;
}
bool solve(int src, int ink, wint flo = wINF) {
	wint f;
	int i, u, v;
	for (tof = 0; tof + wEPS < flo; ) {
		qb = qe = que;
		memset(lev, ~0, n * 4);
		for (lev[*qe++ = src] = 0, see[src] = ptr[src]; qb != qe; ) {
			for (i = ptr[u = *qb++]; ~i; i = next[i]) if (capa[i] > wEPS && !~lev[v = zu[i]]) {
				lev[*qe++ = v] = lev[u] + 1; see[v] = ptr[v];
				if (v == ink) goto au;
			}
		}
		return 0;
	au:	for (; (f = augment(src, ink, flo - tof)) > wEPS; tof += f);
	}
	return 1;
}
}

int N, U[303], D[303], L[303], R[303];
enum {
	UP, DOWN, LEFT, RIGHT
};

int dir[303][303];
bool vis[42][42];

bool resolve()
{
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			vis[i][j] = false;
		}
	}
	bool ret = false;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (vis[i][j]) continue;
			int y = i, x = j;
			vector<pair<int, int> > vc;
			while (y >= 0 && x >= 0 && y < N && x < N) {
				if (vis[y][x]) {
					vector<pair<int, int> > vc2;
					for (int k = 0; k < vc.size(); ++k) {
						if (vc[k] == make_pair(y, x)) {
							for (int l = k; l < vc.size(); ++l) vc2.push_back(vc[l]);
							break;
						}
					}
					swap(vc, vc2);
				}
				vis[y][x] = true;
				vc.push_back({ y, x });
				switch (dir[y][x]) {
				case 0: --y; break;
				case 1: ++y; break;
				case 2: --x; break;
				case 3: ++x; break;
				}
			}
			if (!(y >= 0 && x >= 0 && y < N && x < N)) goto nex;

			ret = true;
			vector<int> cdir;
		//	printf("%d\n", cdir.size());
			for (auto a : vc) cdir.push_back(dir[a.first][a.second]);
			for (int t = 0; t < vc.size(); ++t) {
				auto pt = vc[(t + 1) % vc.size()];
				dir[pt.first][pt.second] = cdir[t];
			}
		}
	nex:
		continue;
	}
	return ret;
}

bool used[44][44];

int main()
{
	scanf("%d", &N);
	if (N > 40) return 0;

	for (int i = 0; i < N; ++i) scanf("%d", U + i);
	for (int i = 0; i < N; ++i) scanf("%d", D + i);
	for (int i = 0; i < N; ++i) scanf("%d", L + i);
	for (int i = 0; i < N; ++i) scanf("%d", R + i);

	MF::init(2 + 4 * N + N * N);
	int s = 4 * N + N * N;
	int t = s + 1;
	auto cell = [&](int y, int x) { return 4 * N + y * N + x; };

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			MF::ae(j, cell(i, j), 1, 0);
			MF::ae(j + N, cell(i, j), 1, 0);
			MF::ae(i + 2 * N, cell(i, j), 1, 0);
			MF::ae(i + 3 * N, cell(i, j), 1, 0);
			MF::ae(cell(i, j), t, 1, 0);
		}
	}
	for (int i = 0; i < N; ++i) {
		MF::ae(s, i, U[i]);
		MF::ae(s, i + 1 * N, D[i]);
		MF::ae(s, i + 2 * N, L[i]);
		MF::ae(s, i + 3 * N, R[i]);
	}
	MF::solve(s, t);
	if (MF::tof != N * N) {
		puts("NO");
		return 0;
	}
	for (int i = 0; i < N * N; ++i) {
		for (int p = MF::ptr[4 * N + i]; p >= 0; p = MF::next[p]) {
			if (MF::zu[p] < 4 * N && MF::capa[p] == 1) {
				dir[i / N][i % N] = MF::zu[p] / N;
			}
		}
	}
/*	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) printf("%d ", dir[i][j]);
		puts("");
	}*/
	while (resolve());
	for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) used[i][j] = false;

	for (int i = 0; i < N * N; ++i) {
		for (int j = 0; j < N; ++j) {
			for (int k = 0; k < N; ++k) {
				if (!used[k][j]) {
					if (dir[k][j] == 0) {
						used[k][j] = true;
						printf("U%d\n", j + 1);
						goto nex;
					}
					break;
				}
			}
			for (int k = N - 1; k >= 0; --k) {
				if (!used[k][j]) {
					if (dir[k][j] == 1) {
						used[k][j] = true;
						printf("D%d\n", j + 1);
						goto nex;
					}
					break;
				}
			}
			for (int k = 0; k < N; ++k) {
				if (!used[j][k]) {
					if (dir[j][k] == 2) {
						used[j][k] = true;
						printf("L%d\n", j + 1);
						goto nex;
					}
					break;
				}
			}
			for (int k = N - 1; k >= 0; --k) {
				if (!used[j][k]) {
					if (dir[j][k] == 3) {
						used[j][k] = true;
						printf("R%d\n", j + 1);
						goto nex;
					}
					break;
				}
			}
		}
	nex:
		continue;

	}

	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:127:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
./Main.cpp:130:48: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i < N; ++i) scanf("%d", U + i);
                                                ^
./Main.cpp:131:48: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i < N; ++i) scanf("%d", D + i);
                                                ^
./Main.cpp:132:48: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i < N; ++i) scanf("%d", L + i);
                                                ^
./Main.cpp:133:48: warning: ignoring return value of ‘int scanf(...

Judge Result