oj.uz

Submission #815486

# Submission time Handle Problem Language Result Execution time Memory
815486 2023-08-08T15:44:48 Z Sohsoh84 None (JOI16_memory2) C++17
100 / 100
 1 ms 480 KB 
#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]);

		for (int i = 0; i < 4; i++) {
			vector<int> ans;
			for (int j = 1; j < 4; j++)
				ans.push_back(ask(f[i], f[(i + j) % 4]));
			
			if (ans[0] == ans[1] && ans[1] == ans[2]) {
				add(f[i], ans[0]);
				break;
			}
		}	
	}

	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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 480 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 348 KB Output is correct