Submission #1002405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002405		zsombor	Ancient Machine 2 (JOI23_ancient2)	C++17	100 / 100	35 ms	1112 KiB

ancient2

#include "ancient2.h"
#include <iostream>
#include <vector>
#include <bitset>
using namespace std;

int n, m = 102;
vector <int> ans(1e3, -1);
vector <bitset <1001>> v(1e3);

void get1(int x) {
	vector <int> a(x + 3, 0);
	vector <int> b(x + 3, 0);
	for (int i = 0; i < x; i++) a[i] = b[i] = i + 1;
	a[x] = x + 1;
	b[x] = x + 2;
	a[x + 1] = b[x + 1] = x + 1;
	a[x + 2] = b[x + 2] = x + 2;
	ans[x] = Query(x + 3, a, b) - x - 1;
}

void solve1() {
	for (int i = 0; i < m - 2; i++) get1(i);
}

void get2(int x) {
	vector <int> s(1, -1);
	s.push_back(1);
	for (int i = x + 1; i < n; i++) s.push_back(ans[i]);
	s.push_back(-1);
	int l = s.size() - 2;

	vector <int> pi(l + 1, 0);
	pi[0] = -1;
	for (int i = 1; i <= l; i++) {
		for (int j = pi[i - 1]; j >= 0; j = pi[j]) {
			if (s[i] == s[j + 1]) { pi[i] = j + 1; break; }
		}
	}

	vector <int> a(l + 1, 0);
	vector <int> b(l + 1, 1);
	for (int i = 1; i <= l; i++) {
		a[i] = (s[i + 1] == 0 ? i + 1 : a[pi[i]]);
		b[i] = (s[i + 1] == 1 ? i + 1 : b[pi[i]]);
	}
	ans[x] = (Query(l + 1, a, b) == l);
}

void solve2() {
	for (int i = n - 1; i > n - m; i--) get2(i);
}

int make_query(int p, int q) {
	vector <int> a(2 * p, 0);
	vector <int> b(2 * p, 0);
	for (int i = 0; i < 2 * p; i++) a[i] = b[i] = (i + 1) % p + i / p * p;
	swap(b[q], b[p + q]);
	return (Query(2 * p, a, b) >= p);
}

void try_add(int p, int q) {
	bitset <1001> b;
	for (int i = 0; i < n; i++) b[i] = int(i % p == q);
	b[1000] = 0;
	for (int i = 0; i < n; i++) if (b[i]) b ^= v[i];

	int k = -1;
	for (int i = 0; i < n; i++) if (b[i]) k = i;
	if (k == -1) return;

	b[1000] = int(b[1000]) ^ make_query(p, q);
	for (int i = 0; i < n; i++) if (v[i][k]) v[i] ^= b;
	v[k] = b;
}

void solve3() {
	for (int i = 0; i < n; i++) {
		if (ans[i] == -1) continue;
		v[i][i] = 1;
		v[i][1000] = ans[i];
	}
	for (int i = 1; i <= 60; i++) {
		for (int j = 0; j < i; j++) {
			try_add(i, j);
		}
	}
	for (int i = 0; i < n; i++) ans[i] = v[i][1000];
}

string Solve(int N) {
	n = N;
	solve1();
	solve2();
	solve3();
	string s;
	for (int i = 0; i < n; i++) s.push_back('0' + ans[i]);
	return s;
}

• Subtask 1: 100 / 100