Submission #1232242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232242		k1r1t0	Ancient Machine 2 (JOI23_ancient2)	C++20	0 / 100	0 ms	320 KiB

ancient2

#include <bits/stdc++.h>

using namespace std;

int Query(int m, vector<int> a, vector<int> b);

const int M = 1000;

bitset<M> bs[M], iv[M];
int sz = 0, val[M], tt[M];
vector<array<int, 2>> vec;

void add(bitset<M> &x, int k, int r) {
	bitset<M> t;
	for (int i = 0; i < M; i++) {
		if (bs[i][i] == 0 || x[i] == 0)
			continue;
		x ^= bs[i];
		t ^= iv[i];
	}
	if (x.count() == 0) return;
	sz++;
	int pos = x._Find_first();
	bs[pos] = x;
	iv[pos] = t;
	iv[pos][vec.size()] = 1;
	vec.push_back({k, r});
}

string build() {
	for (int i = 0; i < M; i++) {
		tt[i] = 0;
		for (int j = 0; j < M; j++)
			if (iv[i][j]) tt[i] ^= val[j];
	}
	string s;
	for (int i = 0; i < M; i++) {
		int xx = tt[i];
		for (int j = i + 1; j < M; j++) {
			if (bs[i][j] == 0) continue;
			bs[i] ^= bs[j];
			xx ^= tt[j];
		}
		s.push_back(xx + '0');
	}
	return s;
}

string Solve(int N) {
	const int len = 108;
	return "";
	for (int i = 1; i <= len - 2; i++) {
		bitset<M> cur;
		for (int j = 0; j < M; j++)
			cur[j] = (j == i - 1);
		add(cur, -1, i);
	}
	return "";
	for (int i = 1; i <= len / 2; i++) {
		for (int k = 0; k < i; k++) {
			bitset<M> cur;
			for (int j = 0; j < M; j++)
				cur[j] = (j % i == k);
			add(cur, i, k);
		}
	}
	return "";
	assert(sz == M);
	assert(sz == (int) vec.size());
	for (int i = 0; i < M; i++) {
		auto [k, r] = vec[i];
		if (k == -1) {
			vector<int> a, b;
			for (int j = 0; j < r; j++) {
				a.push_back(j + 1);
				b.push_back(j + 1);
			}
			b.back() = r + 1;
			a.push_back(r);
			b.push_back(r);
			a.push_back(r + 1);
			b.push_back(r + 1);
			val[i] = Query(a.size(), a, b) - r;
		} else {
			vector<int> a(2 * k), b(2 * k);
			for (int i = 0; i < k; i++) {
				int j = (i + 1) % k;
				for (int t = 0; t < 2; t++) {
					a[2 * i + t] = 2 * j + t;
					if (i != r) {
						b[2 * i + t] = 2 * j + t;
					} else {
						b[2 * i + t] = 2 * j + 1 - t;
					}
				}
			}
			val[i] = Query(a.size(), a, b) % 2;
		}
	}
	return build();
}



























/*

namespace {

using std::exit;
using std::fprintf;
using std::printf;
using std::scanf;

constexpr int N_MAX = 1'000;
constexpr int M_MAX = 1'002;
constexpr int Q_MAX = 1'000;

int N;
char S[N_MAX + 1];

int query_count = 0;
int query_m_max = 0;

void WrongAnswer(int code) {
  printf("Wrong Answer [%d]\n", code);
  exit(0);
}
}  // namespace

int Query(int m, std::vector<int> a, std::vector<int> b) {
  if (++query_count > Q_MAX) WrongAnswer(7);
  if (!(1 <= m && m <= M_MAX)) WrongAnswer(4);
  if ((int)a.size() != m || (int)b.size() != m) WrongAnswer(5);
  for (int i = 0; i < m; i++) {
    if (!(0 <= a[i] && a[i] <= m - 1) || !(0 <= b[i] && b[i] <= m - 1))
      WrongAnswer(6);
  }
  if (m > query_m_max) query_m_max = m;
  int memory = 0;
  for (int i = 0; i < N; i++) {
    if (S[i] == '0') {
      memory = a[memory];
    }
    if (S[i] == '1') {
      memory = b[memory];
    }
  }
  return memory;
}

int main() {
  if (scanf("%d", &N) != 1) {
    fprintf(stderr, "Error while reading input.\n");
    exit(1);
  }
  if (scanf("%s", S) != 1) {
    fprintf(stderr, "Error while reading input.\n");
    exit(1);
  }
  std::string s = Solve(N);
  if ((int)s.size() != N) WrongAnswer(1);
  for (int i = 0; i < N; i++) {
    if (!(s[i] == '0' || s[i] == '1')) WrongAnswer(2);
  }
  for (int i = 0; i < N; i++) {
    if (s[i] != S[i]) WrongAnswer(3);
  }
  printf("Accepted: %d\n", query_m_max);
  return 0;
}
//*/

• Subtask 1: 0 / 100