Submission #1004568

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }

bool bipartiteGraphFromDegreeSequence(const vector<int> &A, const vector<int> &B, vector<pair<int,int>> &res) {
	res.clear();
	if(accumulate(A.begin(), A.end(), 0) != accumulate(B.begin(), B.end(), 0))
		return false;
	vector<pair<int, int>> As(A.size()), Bs(B.size());
	rep(i, A.size()) As[i] = { A[i], i };
	rep(i, B.size()) Bs[i] = { -B[i], i };
	sort(As.begin(), As.end());
	sort(Bs.begin(), Bs.end());
	rep(i, As.size()) {
		if(As[i].first > (int)Bs.size()) {
			res.clear();
			return false;
		}
		rep(j, As[i].first) {
			++ Bs[j].first;
			res.emplace_back(As[i].second, Bs[j].second);
		}
		inplace_merge(Bs.begin(), Bs.begin() + As[i].first, Bs.end());
	}
	rep(j, Bs.size()) if(Bs[j].first != 0) {
		res.clear();
		return false;
	}
	return true;
}

int main() {
	int N;
	while(~scanf("%d", &N)) {
		vector<int> U(N);
		for(int i = 0; i < N; ++ i)
			scanf("%d", &U[i]);
		vector<int> D(N);
		for(int i = 0; i < N; ++ i)
			scanf("%d", &D[i]);
		vector<int> L(N);
		for(int i = 0; i < N; ++ i)
			scanf("%d", &L[i]);
		vector<int> R(N);
		for(int i = 0; i < N; ++ i)
			scanf("%d", &R[i]);
		vector<int> degA(N), degB(N);
		rep(i, N) {
			degA[i] = U[i] + D[i];
			degB[i] = N - (L[i] + R[i]);
		}
		vector<pair<int, int>> edges;
		if(!bipartiteGraphFromDegreeSequence(degA, degB, edges)) {
			puts("NO");
			continue;
		}
		vector<vector<int>> dir(N, vector<int>(N, 2));
		for(auto &&e : edges)
			dir[e.second][e.first] = 0;
		rep(j, N) {
			int numU = U[j];
			rep(i, N) if(dir[i][j] == 0)
				dir[i][j] = numU -- > 0 ? 0 : 1;
		}
		rep(i, N) {
			int numL = L[i];
			rep(j, N) if(dir[i][j] == 2)
				dir[i][j] = numL -- > 0 ? 2 : 3;
		}
		vector<vector<pair<int,int>>> graphs[4];
		rep(k, 4) graphs[k].assign(N, vector<pair<int, int>>());
		rep(i, N) rep(j, N) {
			graphs[0][j].emplace_back(i, j);
			graphs[1][j].emplace_back(N - 1 - i, j);
			graphs[2][i].emplace_back(i, j);
			graphs[3][i].emplace_back(i, N - 1 - j);
		}
		vector<vector<bool>> used(N, vector<bool>(N)), state(N, vector<bool>(N));
		function<bool(int, int)> dfs = [&](int i, int j) -> bool {
			if(used[i][j]) return false;
			if(state[i][j]) {
				state[i][j] = false;
				return true;
			}
			state[i][j] = true;
			int cur_dir = dir[i][j];
			for(auto &&e : graphs[cur_dir][cur_dir < 2 ? j : i]) {
				int ni, nj; tie(ni, nj) = e;
				if(i == ni && j == nj) break;
				if(dfs(ni, nj)) {
					dir[ni][nj] = cur_dir;
					if(state[i][j]) {
						state[i][j] = false;
						return true;
					} else {
						return dfs(i, j);
					}
				}
			}
			state[i][j] = false;
			used[i][j] = true;
			printf("%c%d\n", "UDLR"[dir[i][j]], (dir[i][j] < 2 ? j : i) + 1);
			return false;
		};
		rep(i, N) rep(j, N)
			dfs(i, j);
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:43:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &U[i]);
                      ^
./Main.cpp:46:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &D[i]);
                      ^
./Main.cpp:49:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &L[i]);
                      ^
./Main.cpp:52:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &R[i]);
                      ^

Judge Result