제출 #817083

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
817083		rainboy	Ancient Machine 2 (JOI23_ancient2)	C++17	100 / 100	37 ms	724 KiB

ancient2

/* upsolved with help from GusterGoose27 */
#include "ancient2.h"
#include <cstring>
#include <vector>

using namespace std;

typedef unsigned long long ull;
typedef vector<int> vi;

const int N = 1000, M = 102, L = 64, K = (N + L - 1) / L;

ull vvv[N][K]; int ww[N];

int add(ull *vv) {
	int w = 0;
	for (int i = 0; i < N; i++)
		if ((vv[i / L] & 1ULL << i % L) != 0) {
			if ((vvv[i][i / L] & 1ULL << i % L) != 0) {
				for (int h = i / L; h < K; h++)
					vv[h] ^= vvv[i][h];
				w ^= ww[i];
			} else {
				for (int h = i / L; h < K; h++)
					vvv[i][h] = vv[h];
				ww[i] = w;
				return i;
			}
		}
	return -1;
}

string Solve(int n) {
	string cc(N, '0');
	ull vv[K];
	int rank = 0;
	for (int i = 0; i + 3 <= M; i++) {
		memset(vv, 0, K * sizeof *vv), vv[i / L] |= 1ULL << i % L;
		add(vv), rank++;
		int m = i + 3;
		vi aa(m), bb(m);
		for (int s = 0; s < i; s++)
			aa[s] = bb[s] = s + 1;
		aa[i] = i + 1, bb[i] = i + 2;
		aa[i + 1] = bb[i + 1] = i + 1;
		aa[i + 2] = bb[i + 2] = i + 2;
		if (Query(m, aa, bb) != i + 1)
			ww[i] ^= 1;
	}
	for (int i = N - 1; N - i + 1 <= M; i--) {
		memset(vv, 0, K * sizeof *vv), vv[i / L] |= 1ULL << i % L;
		add(vv), rank++;
		cc[i] = '0';
		int m = N - i + 1;
		vi aa(m), bb(m);
		int f = -1;
		for (int s = 0; s + 1 < m; s++) {
			if (cc[i + s] == '0')
				aa[s] = s + 1, bb[s] = f == -1 ? 0 : bb[f];
			else
				aa[s] = f == -1 ? 0 : aa[f], bb[s] = s + 1;
			f = f == -1 ? 0 : (cc[i + s] == '0' ? aa[f] : bb[f]);
		}
		aa[m - 1] = aa[f], bb[m - 1] = bb[f];
		if (Query(m, aa, bb) != m - 1)
			ww[i] ^= 1, cc[i] = '1';
	}
	for (int c = 1; c * 2 <= M; c++) {
		int m = c * 2;
		vi aa(m), bb(m);
		for (int r = 0; r < c; r++) {
			memset(vv, 0, K * sizeof *vv);
			for (int i = 0; i < N; i++)
				if (i % c == r)
					vv[i / L] |= 1ULL << i % L;
			int i = add(vv);
			if (i != -1) {
				rank++;
				for (int s = 0; s < c; s++) {
					aa[s] = bb[s] = (s + 1) % c;
					aa[c + s] = bb[c + s] = c + (s + 1) % c;
				}
				bb[r] = c + (r + 1) % c;
				bb[c + r] = (r + 1) % c;
				if (Query(m, aa, bb) >= c)
					ww[i] ^= 1;
			}
		}
	}
	if (rank != N)
		return ":(";
	for (int i = N - 1; i >= 0; i--) {
		for (int j = i + 1; j < N; j++)
			if ((vvv[i][j / L] & 1ULL << j % L) != 0)
				ww[i] ^= ww[j];
		cc[i] = ww[i] + '0';
	}
	return cc;
}

• Subtask 1: 100 / 100