Submission #811186

#	Time	Username	Problem	Language	Result	Execution time	Memory
811186		maomao90	Ancient Machine 2 (JOI23_ancient2)	C++17	37 / 100	1461 ms	496 KiB

ancient2

#include "ancient2.h"
#include <bits/stdc++.h>
using namespace std;

#define REP(i, j, k) for (int i = (j); i < (k); i++)
#define RREP(i, j, k) for (int i = (j); i >= (k); i--)

template <class T>
inline bool mnto(T &a, const T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T &a, const T b) {return a < b ? a = b, 1 : 0;}

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int) x.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef tuple<int, int, int> iii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005;
const int MAXN = 500005;

namespace {
	int n;
	char findPrefix(int p) {
		int m = p + 3;
		vi a(m);
		iota(ALL(a), 1);
		a[p + 1] = p + 1;
		a[p + 2] = p + 2;
		vi b = a;
		a[p] = p + 1;
		b[p] = p + 2;
		int r = Query(m, a, b);
		return '0' + (r == p + 2);
	}
	char findSuffix(string s) {
		s = "1" + s;
		int n = SZ(s);
		s += "?";
		int m = n + 1;
		vi a(m), b(m);
		string ps = "";
		REP (i, 0, n + 1) {
			auto get = [&] (char c) {
				string ts = ps + c;
				REP (j, 0, SZ(ts)) {
					bool pos = 1;
					REP (k, 0, SZ(ts) - j) {
						if (ts[j + k] != s[k]) {
							pos = 0;
						}
					}
					if (pos) {
						return SZ(ts) - j;
					}
				}
				return 0;
			};
			a[i] = get('0');
			b[i] = get('1');
			ps += s[i];
		}
		int r = Query(m, a, b);
		return '0' + (r == m - 1);
	}
}

string Solve(int N) {
	n = N;
	string ans(n, '0');
	REP (i, 0, n / 2) {
		ans[i] = findPrefix(i);
	}
	string suf = "";
	RREP (i, n - 1, n / 2) {
		ans[i] = findSuffix(suf);
		suf = ans[i] + suf;
	}
	cerr << ans << '\n';
	return ans;
}

• Subtask 1: 37 / 100