Submission #811214

#	Time	Username	Problem	Language	Result	Execution time	Memory
811214		maomao90	Ancient Machine 2 (JOI23_ancient2)	C++17	100 / 100	78 ms	536 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 = 1001;
const int MAXP = 51;

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

namespace {
	int n;
	bool 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 r == p + 2;
	}
	bool 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 r == m - 1;
	}
	bool findPeriod(int p, int q) {
		int m = p + p;
		vi a(m);
		iota(a.begin(), a.begin() + p, 1);
		iota(a.begin() + p, a.begin() + m, p + 1);
		a[p - 1] = 0;
		a[m - 1] = p;
		vi b = a;
		b[q] += p;
		b[q + p] -= p;
		int r = Query(m, a, b);
		return r >= p;
	}
	bitset<MAXN> basis[MAXN];
	bool insert(bitset<MAXN> bs) {
		REP (i, 0, MAXN) {
			if (!bs[i]) {
				continue;
			}
			if (basis[i].none()) {
				basis[i] = bs;
				return 1;
			}
			bs ^= basis[i];
		}
		return 0;
	}
	int query(bitset<MAXN> bs) {
		REP (i, 0, n) {
			if (!bs[i]) {
				continue;
			}
			if (basis[i].none()) {
				return -1;
			}
			bs ^= basis[i];
		}
		return bs[n];
	}
}

string Solve(int N) {
	n = N;
	string ans(n, '0');
	int rem = 1000;
	REP (i, 0, min(n, 100)) {
		rem--;
		ans[i] = findPrefix(i) + '0';
		bitset<MAXN> bs;
		bs[i] = 1;
		bs[n] = ans[i] - '0';
		insert(bs);
	}
	string suf = "";
	RREP (i, n - 1, max(n - 101, 1)) {
		rem--;
		ans[i] = findSuffix(suf) + '0';
		suf = ans[i] + suf;
		bitset<MAXN> bs;
		bs[i] = 1;
		bs[n] = ans[i] - '0';
		insert(bs);
	}
	REP (_, 0, rem) {
		int p = rnd() % MAXP + 1, q = rnd() % p;
		bitset<MAXN> bs;
		while (1) {
			bs.reset();
			for (int j = q; j < n; j += p) {
				bs[j] = 1;
			}
			if (query(bs) == -1) {
				break;
			}
			p = rnd() % MAXP + 1, q = rnd() % p;
		}
		bool b = findPeriod(p, q);
		bs[n] = b;
		insert(bs);
	}
	REP (i, min(n, 100), max(n - 101, 1)) {
		bitset<MAXN> bs;
		bs[i] = 1;
		ans[i] = query(bs) + '0';
	}
	return ans;
}

• Subtask 1: 100 / 100