Submission #1175955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175955		Zero_OP	Memory 2 (JOI16_memory2)	C++20	100 / 100	0 ms	328 KiB

memory2

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

using namespace std;

namespace{
	int called[100][100];

	int ask(int i, int j){
		if(i > j) swap(i, j);
		if(called[i][j] == -1) called[i][j] = Flip(i, j);
		return called[i][j];
	}
}

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

	memset(called, -1, sizeof(called));

	int best[3];
	best[0] = 0, best[1] = 1, best[2] = 2;
	ask(0, 1); ask(0, 2); ask(1, 2);

	vector<int> answer(2 * N);
	for(int nw = 3; nw < 2 * N; ++nw){
		int p[4] = {best[0], best[1], best[2], nw};
		
		for(int i = 0; i < 4; ++i){
			int mn = ask(p[i], (i == 0 ? p[i+1] : p[i-1])); 
			bool ok = true;
			//check if p[i] is the minimum rank 
			for(int j = 0; j < 4; ++j){
				if(i != j){
					if(ask(p[i], p[j]) != mn){
						ok = false;
						break;
					}
				}
			}

			if(ok){
				answer[p[i]] = mn;
				if(i == 0) best[0] = nw;
				if(i == 1) best[1] = nw;
				if(i == 2) best[2] = nw;
				break;
			}
		}

		// cout << best[0] << ' ' << best[1] << ' ' << best[2] << '\n';
	}

	// cout << "wtf : " << best[0] << ' ' << best[1] << ' ' << best[2] << '\n';
	int x = Flip(best[0], best[1]), y = Flip(best[0], best[2]), z = Flip(best[1], best[2]);

	// cout << "value : " << x << ' ' << y << ' ' << z << '\n';

	if(x == y){
		answer[best[0]] = x;
		answer[best[1]] = answer[best[2]] = z;
	} else if(x == z){
		answer[best[1]] = x;
		answer[best[0]] = answer[best[2]] = y; 
	} else if(y == z){
		answer[best[2]] = y;
		answer[best[0]] = answer[best[1]] = x;
	} else assert(false);

	// for(int i = 0; i < 2 * N; ++i) cout << answer[i] << ' '; cout << '\n';

	vector<pair<int, int>> position(N, make_pair(-1, -1));
	for(int i = 0; i < 2 * N; ++i){
		assert(answer[i] != -1);
		if(position[answer[i]].first == -1) position[answer[i]].first = i;
		else {
			// if(position[answer[i]].second != -1) cout << "wrong shit :" << answer[i] << '\n';
			assert(position[answer[i]].second == -1);
			position[answer[i]].second = i;
		}
	}

	for(int i = 0; i < N; ++i){
		Answer(position[i].first, position[i].second, i);
	}
}

//g++ -o grader grader.cpp Memory2.cpp

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