Submission #1002301

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002301		zsombor	Ancient Machine 2 (JOI23_ancient2)	C++17	0 / 100	27 ms	600 KiB

ancient2

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

int n, m;
vector <int> ans(1e3, -1);

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);
}

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

• Subtask 1: 0 / 100