Submission #1008821

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008821		box	Secret Permutation (RMI19_permutation)	C++17	100 / 100	957 ms	600 KiB

permutation

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

#define ar array
#define sz(v) int(v.size())
typedef long long ll;

const int mxN=256;

#ifndef LOCAL
#include "permutation.h"
#else
int n, p[mxN];
int query(vector<int> v) {
    int x=0;
    assert(sz(v)==n);
    for (int i=0; i<n-1; i++) x+=abs(p[v[i+1]-1]-p[v[i]-1]);
    return x;
}
void answer(vector<int> v) {
    assert(sz(v)==n);
    for (int i=0; i<n; i++) cout<<v[i]<<" \n"[i==n-1];
}

#endif

int N, o[mxN];
int r[mxN];
mt19937 rng(2);
bool used[mxN*2+1];
int a[mxN];

bool rec(int i, int low, int hi) {
    if (hi-low+1>N) return 0;
    if (i==N-1) {
        if (abs(r[N-1])!=abs(a[0]-a[N-1])) return 0;
        int v=*min_element(a,a+N);
        for (int i=0; i<N; i++) a[i]=a[i]-v+1;
        return 1;
    }
    int x=a[i];
    if (x+r[i]<=N*2&&x+r[i]>=0&&!used[x+r[i]]) {
        used[a[i+1]=x+r[i]]=1;
        if (rec(i+1,min(low,a[i+1]),max(hi,a[i+1]))) return 1;
        used[a[i+1]]=0;
    }
    if (x-r[i]<=N*2&&x-r[i]>=0&&!used[x-r[i]]) {
        used[a[i+1]=x-r[i]]=1;
        if (rec(i+1,min(low,a[i+1]),max(hi,a[i+1]))) return 1;
        used[a[i+1]]=0;
    }
    return 0;
}

int gen(int l, int r) {
    return uniform_int_distribution(l,r)(rng);
}

void solve(int n) {
    N=n;
    iota(o,o+N,1);
    for (int i=0; i<N; i++) swap(o[i],o[gen(0,i)]);
    for (int i=0; i<N; i++) {
        rotate(o,o+1,o+N);
        r[i]=query(vector(o,o+N));
    }
    for (int i=0; i<N; i++) o[i]--;
    int s=accumulate(r,r+N,0);
    assert(s%(N-1)==0);
    s/=N-1;
    for (int i=0; i<N; i++) r[i]=s-r[i];
    fill(used,used+N*2+1,0);
    used[a[0]=N]=1;
    assert(rec(0,N,N));
    vector<int> v(N);
    for (int i=0; i<N; i++) v[o[i]]=a[i];
    answer(v);
}

#ifdef LOCAL
int main() {
    cin>>n;
    for (int i=0; i<n; i++) cin>>p[i];
    solve(n);
}
#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