Submission #815477

#	Time	Username	Problem	Language	Result	Execution time	Memory
815477		Sohsoh84	Memory 2 (JOI16_memory2)	C++17	60 / 100	1 ms	468 KiB

memory2

#include "Memory2_lib.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e3 + 10;

#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;

vector<int> rem_inds;
bool flag[MAXN], asked[MAXN][MAXN];
vector<int> vec[MAXN];
int FFF[MAXN][MAXN], N;

inline void add(int ind, int val) {
	vec[val].push_back(ind);
	flag[ind] = true;
	rem_inds.erase(find(rem_inds.begin(), rem_inds.end(), ind));
}

inline int ask(int i, int j) {
	if (i > j) swap(i, j);
	if (!asked[i][j]) {
		asked[i][j] = true;
		FFF[i][j] = Flip(i, j);
	}

	return FFF[i][j];
}

inline void answer() {
	for (int i = 0; i < N; i++) {
		while (int(vec[i].size()) < 2) {
			vec[i].push_back(rem_inds.back());
			rem_inds.pop_back();
		}
		
		Answer(vec[i][0], vec[i][1], i);
	}
}

void Solve(int T, int N_) {
	N = N_;
	if (N == 1) {
		Answer(0, 1, 0);
		return;
	}

	for (int i = 0; i < 2 * N; i++)
		rem_inds.push_back(i);

	while (int(rem_inds.size()) >= 4) {
		vector<int> f;
		for (int i = 0; i < 4; i++)
			f.push_back(rem_inds[i]);

		vector<int> ans = {-1};
		for (int j = 1; j < 4; j++)
			ans.push_back(ask(f[0], f[j]));

		if (ans[1] == ans[2] && ans[2] == ans[3]) {
			add(f[0], ans[1]);
		} else {
			auto ind = min_element(ans.begin() + 1, ans.end()) - ans.begin();
			add(f[ind], ans[ind]);
		}
	}

	vector<int> V1, V2;
	for (int i = 0; i < N; i++) {
		if (int(vec[i].size()) == 1) V1.push_back(i);
		else if (int(vec[i].size()) == 0) V2.push_back(i);
	}

	if (int(V1.size()) == 3) {
		sort(rem_inds.begin(), rem_inds.end());
		do {
			bool flag = true;
			for (int i = 0; i < 3; i++)
				flag &= (ask(vec[V1[i]].front(), rem_inds[i]) == i);
			
			if (flag) {
				for (int i = 0; i < 3; i++)
					vec[V1[i]].push_back(rem_inds[i]);
				
				answer();
				return;
			}
		} while (next_permutation(rem_inds.begin(), rem_inds.end()));
	}

	vector<int> ans;
	for (int i = 0; i < 3; i++)
		ans.push_back(ask(vec[V1[0]].front(), rem_inds[i]));

	if (ans[0] != ans[1] || ans[1] != ans[2]) {
		int val = *max_element(ans.begin(), ans.end());
		for (int i = 0; i < 3; i++) {	
			if (ask(vec[V1[0]].front(), rem_inds[i]) == val) {
				add(rem_inds[i], V1[0]);
				break;
			}
		}

		answer();
		return;
	}

	for (int i = 0; i < 3; i++) {
		if (ask(rem_inds[i], rem_inds[(i + 1) % 3]) == ask(rem_inds[i], rem_inds[(i + 2) % 3])) {
			add(rem_inds[i], V1[0]);
			break;
		}
	}

	answer();
	return;
}

• Subtask 1: 10 / 10
• Subtask 2: 50 / 50
• Subtask 3: 0 / 40