Submission #1054221

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054221		socpite	Secret Permutation (RMI19_permutation)	C++17	27.50 / 100	5062 ms	344 KiB

permutation

#include "permutation.h"
#include<bits/stdc++.h>
using namespace std;

const int maxn = 300;

namespace {
	int n;
	long long D[maxn];
	bool vis[maxn];
	vector<int> crr;
	vector<vector<int>> allans;
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	int prv(int x){
		return x == 0 ? n-1 : x-1;
	}
	int nxt(int x){
		return x == n-1 ? 0 : x+1;
	}
}

void bt(int l, int r){
	if(nxt(r) == l){
		if(abs(crr[l] - crr[r]) != D[l])return;
		allans.push_back(crr);
		return;
	}
	int pr = nxt(r);
	int op1 = crr[r] + D[pr], op2 = crr[r] - D[pr]; 
	if(op1 > n || vis[op1]){
		if(op2 < 1 || vis[op2])return;
		vis[op2] = 1;
		crr[pr] = op2;
		bt(l, pr);
		vis[op2] = 0;
	}
	else if(op2 < 1 || vis[op2]){
		vis[op1] = 1;
		crr[pr] = op1;
		bt(l, pr);
		vis[op1] = 0;
	}
	else {
		int pl = prv(l);
		op1 = crr[l] + D[l], op2 = crr[l] - D[l];
		if(op1 <= n && !vis[op1]){
			crr[pl] = op1;
			vis[op1] = 1;
			bt(pl, r);
			vis[op1] = 0;
		}
		if(op2 >= 1 && !vis[op2]){
			crr[pl] = op2;
			vis[op2] = 1;
			bt(pl, r);
			vis[op2] = 0;
		}
	}
	
}

void solve(int N) {
	n = N;
	long long sum = 0;
	vector<int> P(N);
	crr.resize(N, 0);
	iota(P.begin(), P.end(), 1);
	// shuffle(P.begin(), P.end(), rng);
	for(int i = 0; i < N; i++){
		D[i] = query(P);
		sum += D[i];
		P.push_back(P[0]);
		P.erase(P.begin());
	}
	sum /= N-1;
	for(int i = 0; i < N; i++){
		D[i] = sum - D[i];
		// cout << D[i] << endl;
	}
	allans.clear();

	for(int i = 1; i <= N; i++){
		crr[0] = i;
		vis[i] = 1;
		bt(0, 0);
		vis[i] = 0;
	}
	while(allans.size() > 2){
		shuffle(P.begin(), P.end(), rng);
		vector<vector<int>> nw;
		int chksum = query(P);
		for(auto vec: allans){
			int csum = 0;
			for(int i = 1; i < N; i++)csum += abs(vec[P[i]-1] - vec[P[i-1]-1]);
			if(csum == chksum)nw.push_back(vec);
		}
		allans = nw;
	}
	answer(allans.back());

}

Compilation message (stderr)

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: 8.25 / 15
• Subtask 2: 19.25 / 35
• Subtask 3: 0 / 50