oj.uz

답안 #1002301

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1002301 2024-06-19T12:16:40 Z zsombor Ancient Machine 2 (JOI23_ancient2) C++17
0 / 100
 27 ms 600 KB 
#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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 27 ms 600 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -