Submission #1322395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1322395		apxo	Secret Permutation (RMI19_permutation)	C++20	100 / 100	707 ms	428 KiB

permutation

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#include "permutation.h"
#endif

const int maxn = 305;
int n, a[maxn];
bool vis[maxn];
int cur[maxn];
vector<int> res;
vector<int> p;
bool ans;

#ifdef duc_debug
int query(vector<int> v);
void answer(vector<int> p);
int N, P[maxn];
#endif

mt19937_64 rng(1);

void track(int x) {
  if (ans) return;
  if (x == n) {
    if (abs(cur[n - 1] - cur[0]) != a[n]) return;
    for (int i = 0; i < n; ++i) {
      res[p[i] - 1] = cur[i];
      debug(i, p[i], cur[i]);
    }
    answer(res);
    ans = 1;
    return;
  }
  int vx = cur[x - 1] + a[x], vy = cur[x - 1] - a[x];
  if (vx >= 1 and vx <= n and !vis[vx]) {
    cur[x] = vx;
    vis[vx] = 1;
    track(x + 1);
    vis[vx] = 0;
  }
  if (vy >= 1 and vy <= n and !vis[vy]) {
    cur[x] = vy;
    vis[vy] = 1;
    track(x + 1);
    vis[vy] = 0;
  }
}

void solve(int N) {
  n = N;
  p = vector<int>(n);
  iota(p.begin(), p.end(), 1);
  shuffle(p.begin(), p.end(), rng);
  int tot = 0;
  for (int i = 1; i <= n; ++i) {
    int t = p[0];
    p.erase(p.begin());
    p.push_back(t);
    a[i] = query(p);
    debug(p);
    tot += a[i];
  }
  tot /= (n - 1);
  for (int i = 1; i <= n; ++i) {
    a[i] = tot - a[i];
//    debug(i, a[i]);
  }
  res = vector<int>(n);
  for (int i = 1; i <= n; ++i) {
    vis[i] = 1;
    cur[0] = i;
    track(1);
    vis[i] = 0;
    if (ans) break;
  }
}

#ifdef duc_debug
int query(vector<int> v) {
  int res = 0;
  for (int j = 1; j < (int)v.size(); ++j) {
    res += abs(P[v[j]] - P[v[j - 1]]);
  }
  return res;
}

void answer(vector<int> p) {
  debug(p);
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  cin >> N;
  for (int i = 1; i <= N; ++i) cin >> P[i];
  solve(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