QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#318275#7999. 拉丁方rageOfThunderCompile Error//C++205.2kb2024-01-30 21:47:212024-01-30 21:47:22

Judging History

你现在查看的是最新测评结果

  • [2024-01-30 21:47:22]
  • 评测
  • [2024-01-30 21:47:21]
  • 提交

answer

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma")
// MagicDark
#include <bits/stdc++.h>
#define debug cerr << "[" << __LINE__ << "] "
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> inline void chkmax(T &x, T y) {x = max(x, y);}
template <typename T> inline void chkmin(T &x, T y) {x = min(x, y);}
template <typename T> inline void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	x *= f;
}
const int N = 510;
int n, r, c, a[N][N], cnt[N], id[N];//, res[N][N];
bool vis[N * N];
vector <int> cir;
vector <vector <int>> res;
vector <pair <int, int>> g[N * 2];
void euler(int x) {
	// debug << x << endl;
	while (g[x].size()) {
		auto [y, id] = g[x].back(); g[x].pop_back();
		if (vis[id]) continue;
		vis[id] = true;
		euler(y);
		cir.push_back(id);
	}
}
pair <vector <vector <int>>, vector <vector <int>>> divide(vector <vector <int>> e) {
	int d = e[0].size();
	// F(i, 0, e.size() * 2) g[i].clear();
	F(i, 0, SZ(e))
		F(j, 0, d - 1) {
			int id = i * d + j;
			vis[id] = false;
			// debug << e[i][j] << endl;
			// debug << i << " " << e[i][j] + e.size() << endl;
			g[i].emplace_back(e[i][j] + e.size(), id);
			g[e[i][j] + e.size()].emplace_back(i, id);
		}
	cir.clear();
	F(i, 0, SZ(e))
		if (g[i].size()) euler(i);
	vector <vector <int>> a(e.size()), b(e.size());
	// debug << cir.size() << ' ' << e.size() * d << endl;
	F(i, 0, SZ(cir)) {
		int p = cir[i] / d, q = cir[i] % d;
		// debug << cir[i] << endl;
		((i & 1) ? a[p] : b[p]).push_back(e[p][q]);
	}
	// debug << a[0].size() << " " << b[0].size() << endl;
	return make_pair(a, b);
}
mt19937 mrand(1);
// mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
int tor[N];
// bool vis[N];//, idl[N];
void work(vector <vector <int>> e) {
	int d = e[0].size();
	// F(i, 0, SZ(e)) cout << e[i].size() << ' '; cout << endl;
	// debug << d << endl;
	if (d == 1) {
		vector <int> g;
		for (auto i: e) {
			// assert(i.size());
			g.push_back(i[0]);
		}
		// res.push_back(e[0]);
		res.push_back(g);
		return;
	}
	if (d % 2 == 0) {
		// F(i, 0, SZ(e)) {
		// 	for (int j: e[i])
		// 		cout << i << " " << e.size() + j << endl;
		// }
		auto [x, y] = divide(e);
		// debug << x[0].size() << ' ' << y[0].size() << endl;
		work(x), work(y);
		return;
	}
	F(i, 0, SZ(e)) id[i] = i, tor[i] = -1, vis[i] = false;
	shuffle(id, id + e.size(), mrand);
	// debug << "!\n";
	F(i, 0, SZ(e)) {
		int x = id[i];
		// debug << x << endl;
		vector <int> sta;
		while (x != -1) {
			// debug << x << " " << d << endl;
			// for (int j: e[x]) cout << x << "  " << j << endl;
			int y;
			do {
				y = e[x][mrand() % e[x].size()];
				// debug << y << " " << tor[y] << endl;
			} while (tor[y] == x);
			// debug << y << endl;
			while (vis[y]) {
				vis[sta.back()] = false;
				sta.pop_back();
			}
			vis[y] = true;
			sta.push_back(y);
			x = tor[y];
		}
		int pos = id[i];
		for (int j: sta) swap(pos, tor[j]), vis[j] = false;
	}
	// vector <vector <int>> ee(n);
	vector <int> rres(e.size());
	F(i, 0, SZ(e)) {
		rres[tor[i]] = i;
		e[tor[i]].erase(find(all(e[tor[i]]), i));
	}
	// debug << e[0].size() << endl;
	res.push_back(rres);
	work(e);
}
void zhk() {
	read(n), read(r), read(c);
	F(i, 1, n) cnt[i] = 0;
	F(i, 1, r)
		F(j, 1, c)
			read(a[i][j]), cnt[a[i][j]]++;
	F(i, 1, n)
		if (cnt[i] + n - r + n - c < n) {
			puts("No");
			return;
		}
	if (c < n) {
		vector <vector <int>> e(n);
		F(i, 1, n) cnt[i] = r - cnt[i];
		F(i, 1, r) {
			F(j, 1, n) vis[j] = false;
			F(j, 1, c) vis[a[i][j]] = true;
			F(j, 1, n)
				if (!vis[j]) e[i - 1].push_back(j - 1);//, debug << i - 1 << ' ' << j - 1 << endl;
		}
		// F(j, 1, n) cout << cnt[j] << " "; cout << endl;
		F(i, r, n - 1) {
			F(j, 1, n) id[j] = j;
			sort(id + 1, id + n + 1, [&] (int x, int y) {
				return cnt[x] < cnt[y];
			});
			F(j, 1, n - c) {
				// debug << i << " " << id[j] << endl;
				e[i].push_back(id[j] - 1);
				cnt[id[j]]++;
			}
		}
		// F(j, 1, n) cout << cnt[j] << " "; cout << endl;
		// exit(0);
		res.clear();
		// debug << endl;
		// F(i, 0, SZ(e)) {
		// 	for (int j: e[i])
		// 		cout << j << ' ';
		// 	cout << endl;
		// }
		work(e);
		// debug << endl;
		F(i, c + 1, n)
			F(j, 1, r)
				a[j][i] = res[i - c - 1][j - 1] + 1;
	}
	if (r < n) {
		vector <vector <int>> e(n);
		F(i, 1, n) {
			F(j, 1, n) vis[j] = false;
			F(j, 1, r) vis[a[j][i]] = true;
			F(j, 1, n)
				if (!vis[j]) e[i - 1].push_back(j - 1);
		}
		res.clear();
		// debug << endl;
		work(e);
		F(i, r + 1, n)
			F(j, 1, n)
				a[i][j] = res[i - r - 1][j - 1] + 1;
	}
	puts("Yes");
	F(i, 1, n) {
		F(j, 1, n)
			cout << a[i][j] << ' ';
		cout << '\n';
	}
}
signed main() {
	int _ = 1;
	cin >> _;
	while (_--) zhk();
	return 0;
}
/* why?
*/

Details

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:4:
/usr/include/c++/13/bits/allocator.h: In destructor ‘constexpr std::_Vector_base<int, std::allocator<int> >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = int]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~