Submission #700375

#	Time	Username	Problem	Language	Result	Execution time	Memory
700375		tjd229	Secret Permutation (RMI19_permutation)	C++17	100 / 100	243 ms	280 KiB

permutation

#include  "permutation.h"
#include <vector>
#include <algorithm>
#include <random>
#include <time.h>
using namespace std;


int Tx[257], x[257 + 257];
int use[257];
int N;


bool recon(int ix, int depth, vector<pair<int,int> > &P) {

	while (P.size()) {
		int bk = P.back().first;
		if (P.size() == N) {
			int d = bk - P[0].first;
			if (d < 0) d = -d;
			if (d == x[ix+ 1]) return 1;
			else {
				use[bk] = 0;
				P.pop_back();
				--ix;
			}
		}
		if (P.back().second == 0) {
			P.back().second = 1;
			int nxt = bk + x[ix + 1];
			if (nxt <= N && use[nxt] == 0) {
				P.push_back({nxt,0});
				++ix; use[nxt] = 1;
			}
		}
		else if (P.back().second == 1) {
			P.back().second = 2;
			int nxt = bk - x[ix + 1];
			if (nxt >0 && use[nxt] == 0) {
				P.push_back({ nxt,0 });
				++ix; use[nxt] = 1;
			}
		}
		else {
			use[bk] = 0;
			P.pop_back();
			--ix;
		}		
	}

	return 0;
}
void solve(int N) {
	::N = N;
	int sum = 0;
	vector<int> V;
	for (int i = 1; i <= N; ++i) V.push_back(i);
	/*mt19937 g(random_device);
	shuffle(V.begin(), V.end(),g);*/
	srand(time(0));
	random_shuffle(V.begin(), V.end());

	for (int i = 1; i <= N; ++i) {
		Tx[i] = query(V);
		sum += Tx[i];
		use[i] = 0;
		int bk = V[0];
		for (int j = 1; j < N; ++j) V[j - 1] = V[j];
		V.back() = bk;
	}
	int T = sum / (N - 1);
	int mx = -1;
	int src = 0;
	for (int i = 1; i <= N; ++i) {
		x[N + i] = x[i] = T - Tx[i];

		if (mx < x[i]) {
			mx = x[i];
			src = i - 1;
		}
	}
	if (src == 0) src = N;


	for (int i = 1; i <= N; ++i) {
		//continue;
		if (i + x[src] > N && i - x[src] < 1) continue;
		//printf("%d,%d\n",i,x[src]);
		vector<pair<int, int> > P = { {i,0} };
		use[i] = 1;

		if (recon(src, 1, P)) {
			vector<int> ans(N);
			for (i = 0; i < N; ++i)
				ans[V[(src + i - 1) % N] - 1] = P[i].first;
			//ans[V[i] - 1] = P[i];// , printf("%d,%d\n", V[i], P[i]);

			answer(ans);
			return;
		}
		P.pop_back(); use[i] = 0;
	}
}

Compilation message (stderr)

permutation.cpp: In function 'bool recon(int, int, std::vector<std::pair<int, int> >&)':
permutation.cpp:18:16: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   18 |   if (P.size() == N) {
      |       ~~~~~~~~~^~~~
stub.cpp: In function 'int query(int*)':
stub.cpp:15:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   fscanf(stdin, "%d", &x);
      |   ~~~~~~^~~~~~~~~~~~~~~~~
stub.cpp: In function 'int main(int, char**)':
stub.cpp:48:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |   fscanf(stdin, "%d", &N);
      |   ~~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 35 / 35
• Subtask 3: 50 / 50