# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
239393 | Sorting | Secret Permutation (RMI19_permutation) | C++14 | 5017 ms | 632 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 query(int v[]);
int query(vector<int> v);
void answer(int v[]);
void answer(vector<int> v);
void recursion(const vector<int> &v, const vector<int> &arr, vector<int> &ans, vector<int> &vis, int pos){
if(pos == v.size() - 1){
if(abs(ans[0] - ans[v.size() - 1]) == arr[pos]){
vector<int> x(v.size());
for(int i = 0; i < v.size(); ++i)
x[v[i] - 1] = ans[i];
answer(x);
exit(0);
}
return;
}
int choice1 = ans[pos] + arr[pos];
int choice2 = ans[pos] - arr[pos];
if(choice1 <= v.size() && !vis[choice1]){
ans[pos + 1] = choice1;
vis[choice1] = true;
recursion(v, arr, ans, vis, pos + 1);
ans[pos + 1] = 0;
vis[choice1] = false;
}
if(choice2 >= 1 && !vis[choice2]){
ans[pos + 1] = choice2;
vis[choice2] = true;
recursion(v, arr, ans, vis, pos + 1);
ans[pos + 1] = 0;
vis[choice2] = false;
}
}
void solve(int n){
vector<int> v;
for(int i = 1; i <= n; ++i)
v.push_back(i);
random_shuffle(v.begin(), v.end());
vector<int> arr(n + 1);
for(int i = 0; i < n; ++i){
rotate(v.begin(), v.begin() + 1, v.end());
arr[i] = query(v);
}
int sum = 0;
for(int i = 0; i < n; ++i)
sum += arr[i];
sum /= n - 1;
for(int i = 0; i < n; ++i)
arr[i] = sum - arr[i];
//for(int i = 0; i < n; ++i)
// cout << arr[i] << " ";
//cout << endl;
vector<int> ans(n), vis(n + 1, false);
for(int i = 1; i <= n; ++i){
ans[0] = i;
vis[i] = true;
recursion(v, arr, ans, vis, 0);
ans[0] = 0;
vis[i] = false;
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |