mole

#include "mole.h"
#include <cstdio>
#include <utility>

void makeOneCycle(std::vector<int> &perm) {
	int nrswaps = ask(perm);
	for(int i = 0; i < perm.size() - 1; ++i) {
		std::swap(perm[i], perm[i + 1]);
		for(int i = 0; i < perm.size(); ++i)
			printf("%d ", perm[i]);
		printf("-> query\n");
		if(ask(perm) < nrswaps)
			std::swap(perm[i], perm[i + 1]);
		else
			nrswaps++;
	}
}

int getTriangleSwaps(std::vector<int> perm, int a, int b, int c) {
	int aux = perm[c];
	perm[c] = perm[b];
	perm[b] = perm[a];
	perm[a] = aux;

	return ask(perm);
}

std::vector<int> find_standings(int N) {
	std::vector<int> perm;
	std::vector<int> cycleOrder;
	for(int i = 1; i <= N; ++i)
		perm.push_back(i);

	makeOneCycle(perm);

	cycleOrder.push_back(perm[0], perm[1]);

	for(int i = 2; i < perm.size(); ++i) {
		int st = 1, dr = cycleOrder.size() + 1;
		while(dr - st > 1) {
			int mid = (st + dr) / 2;
			if(getTriangleSwaps(perm, perm[0], perm[cycleOrder[mid]], perm[i]))
				dr = mid;
			else
				st = mid;
		}

		cycleOrder.insert(cycleOrder.begin(), st, perm[i]);
	}

	return rez;
}


grader_mole

#include <iostream>
#include <string>
#include "mole.h"

using namespace std;

int counter;

std::vector<int> rez;

int ask(const vector<int> &perm) {
	int nswaps = 0;

	if(perm.size() != rez.size()) {
		printf("Wrong size!");
		exit(1);
	}

	vector<bool> fr(perm.size() + 1, false);
	for(int i = 0; i < perm.size(); ++i)
		if((perm[i] <= 0 || perm[i] > perm.size()) || fr[perm[i]] == true)
			exit(1);
		else
			fr[perm[i]] = true;

	++counter;
	vector<int> poz(perm.size() + 1, 0);
	vector<bool> viz(perm.size() + 1, false);

	for(int i = 0; i < rez.size(); ++i)
		poz[rez[i]] = i;

	for(int i = 0; i < rez.size(); ++i)
		if(!viz[perm[i]]) {
			nswaps++;
			int nod = i;
			while(!viz[perm[nod]]) {
				viz[perm[nod]] = true;
				nod = poz[perm[nod]];
			}
		}

	return rez.size() - nswaps;
}

void returnAnswer(std::string str, int score) {
	cerr << str;
	cout << score;
}

void checkResult(const std::vector<int> &officialPerm, const std::vector<int> &participantPerm) {
	int i = 0;
	if(participantPerm.size() != officialPerm.size()) {
		cerr << "Wrong size!";
		fprintf(stderr, "Wrong size!");
		printf("0");
	}

	while(i < participantPerm.size() && participantPerm[i] == officialPerm[i])
		++i;

	if(i < participantPerm.size())
		returnAnswer("Wrong perm!", 0);
	else
		returnAnswer("OK! [" + std::to_string(counter) + "]", 1);
}

int main() {
	int N;

	cin >> N;
	rez.resize(N);
	for(int i = 0; i < N; ++i)
		cin >> rez[i];

	vector<int> participantOutput;
	participantOutput = find_standings(N);

	checkResult(participantOutput, rez);

	return 0;
}



mole.h

#include <vector>

int ask(const std::vector<int> &guess);
std::vector<int> find_standings(int N);