| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 287399 | 2020-08-31T16:41:25 Z | eohomegrownapps | Secret Permutation (RMI19_permutation) | C++14 | 0 ms | 0 KB |
#include "permutation.h"
#include <bits/stdc++.h>
using namespace std;
//int query(std::vector<int> v);
//void answer(std::vector<int> v);
vector<int> getDifferences(vector<int> perm){
deque<int> dq(perm.begin(),perm.end());
int n = perm.size();
vector<int> vals(n);
int tot = 0;
for (int i = 0; i<n; i++){
vector<int> q(dq.begin(),dq.end());
/*for (int x : q){
cout<<x<<' ';
}cout<<endl;*/
vals[i]=query(q);
tot+=vals[i];
dq.push_back(dq.front());
dq.pop_front();
}
vector<int> ans(n);
ans[n-1]=tot/(n-1) - vals[0];
//cout<<ans[n-1]<<'\n';
int prev = ans[n-1];
vals.push_back(vals[0]);
for (int i = 0; i<n; i++){
ans[i] = prev - (vals[i+1]-vals[i]);
prev = ans[i];
}
return ans;
}
vector<bool> used;
stack<int> minv;
stack<int> maxv;
vector<int> values;
vector<int> v1;
vector<int> v1ans;
int curv = 0;
int nv;
int evals = 0;
bool rec(int ind){
evals++;
if (evals>1000000){
return false;
}
/*cout<<ind<<endl;
for (int i : values){
cout<<i<<' ';
}cout<<endl;*/
// add element ind
if (ind==nv){
if (abs(values[nv-1]-values[0])==v1[nv-1]){
/*cout<<"solution:"<<endl;
for (int i : values){
cout<<i<<' ';
}cout<<'\n';*/
if (v1ans[0]!=-1){
return false;
}
v1ans = v1;
return true;
}
return true;
}
//used[nv+x]
//can we add?
bool works = true;
int qtmp = values[ind-1]+v1[ind-1];
//cout<<"check increase "<<qtmp<<endl;
if (max(qtmp,maxv.top())-minv.top()<nv && !used[nv+qtmp]){
// try it
bool popfrom = false;
if (qtmp>maxv.top()){
popfrom = true;
maxv.push(qtmp);
}
values[ind]=qtmp;
used[nv+qtmp]=true;
if (!rec(ind+1)){
works = false;
}
used[nv+qtmp]=false;
if (popfrom){
maxv.pop();
}
}
if (!works){
return false;
}
if (ind==1){
return true;/
}
v1[ind-1]=-v1[ind-1];
qtmp = values[ind-1]+v1[ind-1];
//cout<<"check decrease "<<qtmp<<endl;
if (maxv.top()-min(qtmp,minv.top())<nv && !used[nv+qtmp]){
// try it
bool popfrom = false;
if (qtmp<minv.top()){
popfrom = true;
minv.push(qtmp);
}
values[ind]=qtmp;
used[nv+qtmp]=true;
if (!rec(ind+1)){
works = false;
}
used[nv+qtmp]=false;
if (popfrom){
minv.pop();
}
}
v1[ind-1]=-v1[ind-1];
return works;
}
void solve(int n){
vector<int> q1(n);
for (int i = 0; i<n; i++){
q1[i]=i+1;
}
v1 = getDifferences(q1);
/*for (int i : v){
cout<<i<<' ';
}cout<<endl;*/
vector<int> q2;
for (int i = 1; i<=n; i+=2){
q2.push_back(i);
}
for (int i = 2; i<=n; i+=2){
q2.push_back(i);
}
used.resize(2*n+1);
used[n]=true;
values.resize(n);
v1ans.resize(n,-1);
nv = n;
minv.push(0);
maxv.push(0);
bool rc = rec(1);
//cout<<rc<<'\n';
if (rc==false){
for (int i = 0; i<n; i++){
v1[i]=abs(v1[i]);
}
vector<int> v2 = getDifferences(q2);
for (int i = 0; i<n-1; i++){
int tot;
if (i%2==0){
//cout<<"query "<<i/2<<'\n';
tot = v2[i/2];
} else {
//cout<<"query "<<(n+1)/2+i/2<<'\n';
tot = v2[(n+1)/2+i/2];
}
//cout<<tot<<'\n';
//cout<<v1[i]<<' '<<v1[i+1]<<'\n';
if (abs(v1[i]+v1[i+1])!=tot){
v1[i+1]=-v1[i+1];
}
}
} else {
v1 = v1ans;
}
/*for (int i : v1){
cout<<i<<' ';
}cout<<endl;*/
int cur = 0;
int mn = 0;
for (int i = 0; i<n-1; i++){
cur+=v1[i];
mn=min(cur,mn);
}
vector<int> ans(n);
ans[0]=1-mn;
for (int i = 1; i<n; i++){
ans[i]=ans[i-1]+v1[i-1];
}
/*for (int i : ans){
cout<<i<<' ';
}cout<<'\n';*/
answer(ans);
}