Submission #820742

#	Time	Username	Problem	Language	Result	Execution time	Memory
820742		ono_de206	Ancient Machine 2 (JOI23_ancient2)	C++17	0 / 100	31 ms	332 KiB

ancient2

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

#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

//#define int long long

typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

int n;
vector<int> a, b;
string ask, ans;

void solve(int l, int r) {
	if(l > r) return;
	if(l == r) {
		int m = a.size();
		a.pb(m + 1); a.pb(m + 1);
		b.pb(m); b.pb(m + 1);
		if(Query(m, a, b) == m + 1) ans.back() = '0';
		else ans.back() = '1';
		for(int i = 0; i < 2; i++) {
			a.pop_back();
			b.pop_back();
		}
		return;
	}
	int m = (l + r) / 2;
	vector<int> _a = a, _b = b;
	for(int i = l; i <= m; i++) {
		int sz = _a.size();
		_a.pb(sz + 2);
		_b.pb(sz + 1);
		for(int j = 0; j < 2; j++) {
			_a.pb(sz + j + 1);
			_b.pb(sz + j + 1);
		}
		int l = Query((int)_a.size(), _a, _b);
		if(l == sz + 2) ans[i] = '0';
		else ans[i] = '1';
		for(int j = 0; j < 3; j++) {
			_a.pop_back();
			_b.pop_back();
		}
		_a.pb(sz + 1);
		_b.pb(sz + 1);
	}
	int ls = -1;
	for(int i = l + 1; i <= m; i++) {
		int sz = (int)a.size();
		if(ans[i] != ans[i - 1]) {
			if(ans[i] == '0') {
				b.pb(sz);
				a.pb(sz + 1);
			} else {
				a.pb(sz);
				b.pb(sz + 1);
			}
			ls = i;
			i++;
		}
	}
	if(ls == m) {
		solve(m + 1, r);
		return;
	}
	_a = a;
	_b = b;
	int sz = (int)a.size();
	if(ans[m] == '0') {
		_a.pb(sz);
		_b.pb(sz + 1);
	} else {
		_b.pb(sz);
		_a.pb(sz + 1);
	}
	while(_a.size() < 504) {
		int pp = (int)_a.size();
		_a.pb(pp + 1);
		_b.pb(pp + 1);
	}
	_a.pb(504);
	_b.pb(504);
	assert((int)_a.size() == 505);
	int q = Query((int)a.size(), a, b);
	if(q == sz) {
		for(int i = m + 1; i <= r; i++) {
			ans[i] = ans[m];
		}
		return;
	}
	int len = q - sz - 1;
	if(ans[m] == '0') {
		a.pb(sz);
		b.pb(sz + 1);
	} else {
		b.pb(sz);
		a.pb(sz + 1);
	}
	for(int i = m + 1; i <= r - len - 1; i++) {
		ans[i] = ans[m];
	}
	ans[r - len] = ans[m] ^ '0' ^ '1';
	solve(r - len + 1, r);
}

string Solve(int _n) {
	n = _n;
	ans = string(n, '0');
	solve(0, n - 1);
	return ans;
}

• Subtask 1: 0 / 100