| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 637789 | ogibogi2004 | Secret Permutation (RMI19_permutation) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "permutationc.h"
#include<bits/stdc++.h>
using namespace std;
mt19937 mt(69);
/*vector<int>p;
int query(vector<int>v)
{
int ans=0;
for(int i=1;i<v.size();i++)
{
ans+=abs(p[v[i]]-p[v[i-1]]);
}
return ans;
}
void answer(vector<int>v)
{
for(auto xd:v)cout<<xd<<" ";
cout<<endl;
}*/
int val[256];
int dif1[256];
int dif2[256];
int c[256];
int n;
void solve(int N)
{
n=N;
vector<int>v1;
for(int i=0;i<n;i++)v1.push_back(i);
vector<int>answers;
answers.push_back(query(v1));
for(int i=1;i<n;i++)
{
v1.clear();
for(int j=i;j<n;j++)v1.push_back(j);
for(int j=0;j<i;j++)v1.push_back(j);
answers.push_back(query(v1));
}
int sum=0;
for(auto xd:answers)sum+=xd;
sum/=(n-1);
//cout<<sum<<endl;
for(int i=0;i<n;i++)
{
dif1[i]=sum-answers[i];
}
v1.clear();
answers.clear();
vector<int>v2;
for(int i=0;i<n;i+=2)v2.push_back(i);
for(int i=1;i<n;i+=2)v2.push_back(i);
for(int i=0;i<v2.size();i++)
{
v1.clear();
for(int j=i;j<v2.size();j++)v1.push_back(v2[j]);
for(int j=0;j<i;j++)v1.push_back(v2[j]);
answers.push_back(query(v1));
}
sum=0;
for(auto xd:answers)sum+=xd;
sum/=(n-1);
for(int i=0;i<v2.size();i++)
{
dif2[v2[i]]=sum-answers[i];
}
vector<int>ans(n,0);
ans[1]=ans[0]+dif1[1];
c[1]=1;
for(int i=2;i<ans.size();i++)
{
if(dif2[i]==dif1[i-1]+dif1[i])
{
c[i]=c[i-1];
}
else c[i]=-c[i-1];
ans[i]=ans[i-1]+c[i]*dif1[i];
}
int minans=0;
for(int i=0;i<ans.size();i++)minans=min(minans,ans[i]);
for(int i=0;i<ans.size();i++)
{
ans[i]-=minans;
ans[i]+=1;
}
/*cout<<"difs:\n";
for(int i=0;i<n;i++)
{
cout<<dif1[i]<<" ";
}
cout<<endl;
for(int i=0;i<n;i++)
{
cout<<dif2[i]<<" ";
}
cout<<endl;
cout<<endl;*/
answer(ans);
}
/*int main()
{
int N;
cin>>N;
for(int i=0;i<N;i++)
{
int x;
cin>>x;
p.push_back(x);
}
solve(N);
}*/