Submission #817047

#	Time	Username	Problem	Language	Result	Execution time	Memory
817047		rainboy	Ancient Machine 2 (JOI23_ancient2)	C++17	37 / 100	65 ms	508 KiB

ancient2

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

using namespace std;

typedef vector<int> vi;

const int N = 1000;

string Solve(int n) {
	string cc(N, 0);
	for (int i = 0; i < N / 2; i++) {
		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;
		cc[i] = Query(m, aa, bb) == i + 1 ? '0' : '1';
	}
	for (int i = N - 1; i >= N / 2; i--) {
		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)
			cc[i] = '1';
	}
	return cc;
}

• Subtask 1: 37 / 100