| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1145577 | thieunguyenhuy | Secret Permutation (RMI19_permutation) | C++20 | 0 ms | 0 KiB |
#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(chrono::high_resolution_clock::now().time_since_epoch().count());
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> P = {-1, 1, 2, 3, 4, 5};
// int query(vector<int> V) {
// int sum = 0;
// for (int i = 0; i + 1 < V.size(); ++i) {
// sum += abs(P[V[i]] - P[V[i + 1]]);
// }
// return sum;
// }
// void answer(vector<int> P) {
// for (auto &x : P) cerr << x << ' ';
// cerr << '\n';
// }
// #endif
int custom_query(vector<int> v) {
for (int i = 0; i < v.size(); ++i) V[i] = v[i];
return query(V);
}
void answer(vector<int> p) {
for (int i = 0; i < p.size(); ++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 = true;
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;
vis.set(value), p[v[index]] = value;
backtrack(index + 1, v, p);
vis.reset(value);
}
}
void solve(int _n) {
n = _n;
vector<int> v(n); iota(v.begin(), v.end(), 1);
// 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] = query(v), total += sum[i];
rotate(v.begin(), v.begin() + 1, v.end());
}
total /= (n - 1);
// 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);
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);
answer(p);
}
#ifdef hwe
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
solve(5);
cerr << '\n'; return 0;
}
#endif