Submission #1272876

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272876		DeathIsAwe	Library (JOI18_library)	C++20	0 / 100	14 ms	432 KiB

library

#include <bits/stdc++.h>
#include "library.h"
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define ll long long
using namespace std;
int n;


int recurfind(int a, vector<int> possible) {
	if (possible.size() == 1) return possible[0];
	vector<int> m(n);
	for (int i=0;i<n;i++) m[i] = 0;
	for (int i=0;i<((int)possible.size())/2;i++) m[possible[i]] = 1;
	int val1 = Query(m);
	m[a] = 1;
	int val2 = Query(m);
	vector<int> newvec;
	if (val1 == val2) {
		for (int i=0;i<((int)possible.size())/2;i++) newvec.pb(possible[i]);
	} else {
		for (int i=((int)possible.size())/2;i<possible.size();i++) newvec.pb(possible[i]);
	}
	return recurfind(a, newvec);
}


void Solve(int N) {
	n = N;
	vector<int> m(n);
	vector<int> zeroright, zeroleft;
	vector<int> curvals;
	for (int i=1;i<n;i++) curvals.pb(i);
	zeroright.pb(recurfind(0, curvals));
	curvals.erase(find(curvals.begin(), curvals.end(), zeroright[0]));
	while (curvals.size() != 0) {
		int prev = zeroright[zeroright.size() - 1];
		int adj = recurfind(prev, curvals);
		for (int i=0;i<n;i++) {
			if (i == adj || i == prev) {
				m[i] = 1;
			} else {
				m[i] = 0;
			}
		}
		if (Query(m) == 1) {
			curvals.erase(find(curvals.begin(), curvals.end(), adj));
			zeroright.pb(adj);
		} else {
			break;
		}
	}
	if (curvals.size() != 0) {
		zeroleft.pb(recurfind(0, curvals));
		curvals.erase(find(curvals.begin(), curvals.end(), zeroleft[0]));
		while (curvals.size() != 0) {
			int prev = zeroleft[zeroleft.size() - 1];
			int adj = recurfind(prev, curvals);
			curvals.erase(find(curvals.begin(), curvals.end(), adj));
			zeroleft.pb(adj);
		}
	}


	vector<int> ansvec;
	reverse(zeroleft.begin(), zeroleft.end());
	for (int i: zeroleft) ansvec.pb(i + 1);
	ansvec.pb(1);
	for (int i: zeroright) ansvec.pb(i + 1);
	Answer(ansvec);
}

• Subtask 1: 0 / 19
• Subtask 2: 0 / 81