Submission #810362

#	Time	Username	Problem	Language	Result	Execution time	Memory
810362		model_code	Ancient Machine 2 (JOI23_ancient2)	C++17	0 / 100	53 ms	848 KiB

ancient2

#include "ancient2.h"
#include <bits/stdc++.h>
 
#define MAX_N 1000
#define M_UPPERBOUND 102
 
using bitvec = std::bitset<MAX_N>;
 
struct basis_manager {
	std::vector<std::pair<int, bitvec> > basis;
	bool add(bitvec v) {
		for (auto i : basis) if (v[i.first]) v ^= i.second;
		if (v.any()) {
			basis.push_back({v._Find_first(), v});
			return true;
		}
		return false;
	}
};
 
// {mod, remainder, actual 01 vector}
// {-1, i,          actual 01 vector} : i-th
// {-2, i,          actual 01 vector} : i-th from the back
std::vector<std::tuple<int, int, bitvec> > list_needed_vecs(int n) {
	std::vector<std::vector<std::tuple<int, int, bitvec> > > cands(M_UPPERBOUND + 1);
	// periodic
	for (int mod = 1; mod <= M_UPPERBOUND / 2; mod++) {
		for (int rem = 0; rem < mod; rem++) {
			bitvec x;
			for (int i = rem; i < n; i += mod) x[i] = 1;
			cands[2 * mod].push_back(std::make_tuple(mod, rem, x));
		}
	}
	// prefix
	for (int i = 0; i + 3 <= M_UPPERBOUND; i++) {
		bitvec x;
		x[i] = 1;
		cands[i + 3].push_back(std::make_tuple(-1, i, x));
	}
	// suffix
	for (int i = 0; i + 2 <= M_UPPERBOUND; i++) {
		bitvec x;
		x[n - 1 - i] = 1;
		cands[i + 2].push_back({-2, i, x});
	}
	basis_manager basis;
	std::vector<std::tuple<int, int, bitvec> > res;
	for (int i = 0; i <= M_UPPERBOUND; i++) {
		for (auto j : cands[i]) {
			if (basis.add(std::get<2>(j))) res.push_back(j);
			if ((int) basis.basis.size() == n) break;
		}
		if ((int) basis.basis.size() == n) break;
	}
	return res;
}
std::vector<bool> solve_linear_equation(std::vector<bitvec> &a, std::vector<bool> &b) {
	int n = a.size();
	for (int i = 0; i < n; i++) {
		int id = -1;
		for (int j = i; j < n; j++) if (a[j][i]) { id = j; break; }
		assert(id != -1);
		std::swap(a[i], a[id]);
		swap(b[i], b[id]);
		for (int j = 0; j < n; j++) if (j != i && a[j][i]) a[j] ^= a[i], b[j] = b[j] ^ b[i];
	}
	return b;
}
 
 
std::string Solve(int n) {
	auto list = list_needed_vecs(n);
	
	std::vector<bitvec> mat;
	std::vector<bool> res;
	std::vector<bool> back_res;
	for (auto i : list) {
		int mod = std::get<0>(i);
		int rem = std::get<1>(i);
		auto query_mod = [&] () {
			int m = mod * 2;
			std::vector<int> a(m), b(m);
			for (int j = 0; j < mod; j++) {
				int next = (j + 1) % mod;
				a[j] = b[j] = next;
				a[j + mod] = b[j + mod] = next + mod;
				if (j == rem) std::swap(b[j], b[j + mod]);
			}
			return Query(m, a, b) >= mod;
		};
		auto query_forward = [&] () {
			int m = rem + 3 + 3;
			std::vector<int> a(m), b(m);
			for (int j = 0; j < rem + 3; j++) a[j] = b[j] = j + 1;
			a[rem + 3] = rem + 1 + 3;
			b[rem + 3] = rem + 2 + 3;
			a[rem + 1 + 3] = b[rem + 3 + 1] = rem + 3 + 1;
			a[rem + 2 + 3] = b[rem + 3 + 2] = rem + 3 + 2;
			return Query(m, a, b) == rem + 2 + 3;
		};
		auto query_back = [&] () {
			assert(rem == (int) back_res.size());
			back_res.insert(back_res.begin(), 0);
			int m = rem + 2;
			std::vector<int> a(m), b(m);
			for (int i = 0; i <= rem + 1; i++) {
				auto get = [&] (bool next) {
					auto cur = std::vector<bool>(back_res.begin(), back_res.begin() + i);
					cur.push_back(next);
					for (int j = std::min(rem + 1, i + 1); j; j--)
						if (std::vector<bool>(cur.end() - j, cur.end()) ==
							std::vector<bool>(back_res.begin(), back_res.begin() + j)) return j;
					return 0;
				};
				a[i] = get(0);
				b[i] = get(1);
			}
			bool res = Query(m, a, b) != rem + 1;
			back_res[0] = res;
			return res;
		};
		mat.push_back(std::get<2>(i));
		res.push_back(mod >= 1 ? query_mod() : mod == -1 ? query_forward() : query_back());
	}
	res = solve_linear_equation(mat, res);
	
	std::string res_str;
	for (auto i : res) res_str.push_back('0' + i);
	
	return res_str;
}

• Subtask 1: 0 / 100