# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
259542 | dantoh000 | Secret Permutation (RMI19_permutation) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "permutationc.h"
using namespace std;
int N;
int d[257];
int vis[257];
int P[257];
bool findperm(int id){
if (id == N) return true;
int last = P[id-1];
int dif = d[id];
//printf("%d: %d +- %d\n",id,last,dif);
int cur = last+dif;
if (cur >= 1 && cur <= N && !vis[cur]){
P[id] = cur;
vis[cur] = 1;
if (findperm(id+1)) return true;
vis[cur] = 0;
P[id] = 0;
}
cur = last-dif;
if (cur >= 1 && cur <= N && !vis[cur]){
P[id] = cur;
vis[cur] = 1;
if (findperm(id+1)) return true;
vis[cur] = 0;
P[id] = 0;
}
return false;
}
void query(vector<int> q){
int a[N];
for (int i = 0; i < N; i++){
a[i] = q[i];
}
return query(a);
}
void answer(vector<int> q){
int a[N];
for (int i = 0; i < N; i++){
a[i] = q[i];
}
answer(a);
}
void solve(int _N){
N = _N;
vector<int> q;
for (int i = 1; i <= N; i++){
q.push_back(i);
}
d[N] = query(q);
for (int j = N-1; j >= 1; j--){
q.insert(q.begin(),q.back());
q.pop_back();
d[j] = query(q);
}
int sum = 0;
for (int i = 1; i <= N; i++){
sum += d[i];
}
assert(sum % (N-1) == 0);
sum /= N-1;
for (int i = 1; i <= N; i++){
d[i] = sum-d[i];
//printf("%d ",d[i]);
//assert(d[i] == abs(ans[i-1]-ans[i%N]));
}
//printf("\n");
for (int i = 1; i <= N; i++){
vis[i] = 1;
P[0] = i;
if (findperm(1)){
vector<int> ANS;
for (int i = 0; i < N; i++) ANS.push_back(P[i]);
answer(ANS);
return;
}
vis[i] = 0;
}
}