# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
685460 | dranaya_dusha | Secret Permutation (RMI19_permutation) | C++17 | 1 ms | 336 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.
//#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
////#define int long long
//#define mp make_pair
//#define pb push_back
//#define fi first
//#define se second
//#define pii pair <int, int>
#include "permutation.h"
using namespace std;
vector<int> ans(300), q(300), v;
int n;
vector<int> used;
bool check (int p)
{
used[ans[p]]=1;
if (p==n && abs(ans[p] - ans[1] ) == q[n])
{
vector<int> tut(n);
for (int i=1; i<=n; i++)
tut[v[i-1]-1]=ans[i];
answer(tut);
exit(0);
}
else
{
if (ans[p]+q[p]<=n && ans[p]+q[p] > 0 && !used[ans[p]+q[p]])
{
ans[p+1]=ans[p]+q[p];
// used[ans[v[p]-1]+q[i]]=1;
check(p+1);
}
if (ans[p]-q[p] > 0 && ans[p]-q[p] <= n && !used[ans[p]-q[p]])
{
ans[p+1]=ans[p]-q[p];
// used[ans[v[p]-1]+q[i]]=1;
check(p+1);
}
used[ans[p]]=0;
ans[p]=0;
}
}
void solve(int nn)
{
n=nn;
for (int i=1; i<=n; i++)
v.push_back(i);
srand(time(NULL));
random_shuffle(v.begin(), v.end());
for(int i=1; i<=n; i++)
{
rotate(v.begin(),v.begin()+1,v.end());
q[i] = query(v);
}
// for (int i=0; i<n; i++)
// cout << q[i] << ' ';
rotate(v.begin(),v.begin()+1,v.end());
int sum=0;
for(int i=1; i<=n; i++)
{
sum+=q[i];
}
sum/=(n-1);
for(int i=1; i<=n; i++) q[i]=(sum-q[i]);
q[n+1]=q[1];
for(int i=1; i<=n; i++)
q[i]=q[i+1];
ans.assign(n+10, 0);
for (int i=1; i<=n; i++)
{
used.assign(n+10, 0);
ans.assign(n+10, 0);
ans[1]=i;
check(1);
}
}
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... |