Submission #1145594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145594		thieunguyenhuy	Secret Permutation (RMI19_permutation)	C++20	100 / 100	460 ms	428 KiB

permutation

#ifndef hwe
	#include "permutationc.h"
#endif

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

#define POPCOUNT(n) (__builtin_popcountll((n)))
#define CLZ(n) (__builtin_clzll((n)))
#define CTZ(n) (__builtin_ctzll((n)))
#define LOG(n) (63 - __builtin_clzll((n)))
#define BIT(n, i) (((n) >> (i)) & 1ll)
#define MASK(i) (1ll << (i))
#define FLIP(n, i) ((n) ^ (1ll << (i)))
#define ON(n, i) ((n) | MASK(i))
#define OFF(n, i) ((n) & ~MASK(i))

#define Int __int128
#define fi first
#define se second

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long long, int> pli;
typedef pair<int, long long> pil;
typedef vector<pair<int, int>> vii;
typedef vector<pair<long long, long long>> vll;
typedef vector<pair<long long, int>> vli;
typedef vector<pair<int, long long>> vil;

template <class T1, class T2> bool maximize(T1 &x, T2 y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}
template <class T1, class T2> bool minimize(T1 &x, T2 y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template <class T> void remove_duplicate(vector<T> &ve) {
    sort (ve.begin(), ve.end());
    ve.resize(unique(ve.begin(), ve.end()) - ve.begin());
}

mt19937_64 rng(1);
template <class T1, class T2> T1 random(T1 l, T2 r) {
    return uniform_int_distribution<T1>(l, r)(rng);
}
template <class T> T random(T r) {
    return rng() % r;
}

const int N = 256 + 5;
const int MOD = 1e9 + 7;
const int inf = 1e9;
const long long INF = 1e18;

int n;
bool found = false;
int sum[N], d[N], V[N], P[N];
bitset<N> vis;

#ifdef hwe
const vector<int> myP = {-1, 4, 5, 2, 1, 3};
const int nn = 5;

int query(int V[]) {
	int sum = 0;
	for (int i = 0; i + 1 < nn; ++i) {
		sum += abs(myP[V[i]] - myP[V[i + 1]]);
	}
	return sum;
}
void answer(int perm[]) {
	for (int i = 0; i < nn; ++i) cerr << perm[i] << ' ';
	cerr << '\n';
}
#endif

int myquery(vector<int> v) {
	for (int i = 0; i < n; ++i) V[i] = v[i];
	return query(V);
}
void myanswer(vector<int> p) {
	for (int i = 0; i < n; ++i) P[i] = p[i];
	answer(P);
}

void backtrack(int index, vector<int> &v, vector<int> &p) {
	if (found) return;

	if (index == n - 1) {
		found = (abs(p[v[n - 2]] - p[v[n - 1]]) == d[index]);
		return;
	}

	int pre = p[v[(index - 1 + n) % n]];
	for (int value : {pre - d[index], pre + d[index]}) {
		if (value <= 0 || value > n || vis[value]) continue;
		p[v[index]] = value, vis.set(value);
		backtrack(index + 1, v, p);
		vis.reset(value);
		if (found) break;
	}
}

void solve(int _n) {
	n = _n;
	vector<int> v(n); iota(v.begin(), v.end(), 1);
	shuffle(v.begin(), v.end(), rng);
	// for (auto &x : v) cerr << x << ' ';
	// cerr << '\n';

	// s1 = abs(p1 - p2) + abs(p2 - p3) + ... + abs(pn-1 - pn)
	// s2 = abs(p2 - p3) + abs(p3 - p4) + ... + abs(pn - p1)
	// s3 = abs(p3 - p4) + abs(p4 - p5) + ... + abs(pn - p1) + abs(p1 - p2)
	// sn = abs(pn - p1) + abs(p1 - p2) + ... + abs(pn-2 - pn-1)
	// Each differences of adjacent elements is added exactly (n-1) times
	// s1 + s2 + ... + sn = (n-1) * (abs(p1-p2) + abs(p2-p3) + ... + abs(pn-1-pn) + abs(pn-p1))

	int total = 0;
	for (int i = 0; i < n; ++i) {
		sum[i] = myquery(v), total += sum[i];
		rotate(v.begin(), v.begin() + 1, v.end());
	}
	assert(total % (n - 1) == 0);
	total /= (n - 1);

	// cerr << "Total = " << total << '\n';

	// d1 = pn - p1, d2 = p1 - p2, d3 = p2 - p3, ..., dn = pn-1 - pn
	for (int i = 0; i < n; ++i) {
		d[i] = total - sum[i];
		--v[i];
	}

	// Try each value for pn
	vector<int> p(n, -1);
	for (int value = 1; value <= n; ++value) {
		p[v[n - 1]] = value, vis.set(value);
		found = false, backtrack(0, v, p);
		vis.reset(value);
		if (found) break;
	}

	assert(found);
	myanswer(p);
}

#ifdef hwe
signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    for (int _ = 0; _ < 10; ++_) solve(5);

    cerr << '\n'; return 0;
}
#endif

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