# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
463775 | mosiashvililuka | Secret Permutation (RMI19_permutation) | C++14 | 2743 ms | 200 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 a,b,c,d,e,i,j,ii,jj,zx,xc,p[1009],pi,ONE,LAST;
vector <int> v,vv,ans;
void solve(int N);
int query(std::vector<int> V);
void answer(std::vector<int> P);
void Fill(vector <int>& q){
int FX[280];
for(int h=0; h<=a+1; h++){
FX[h]=0;
}
for(int h=0; h<q.size(); h++){
FX[q[h]]=1;
}
for(int h=1; h<=a; h++){
if(FX[h]==0){
q.push_back(h);
}
}
}
void solve(int N){
a=N;
for(i=1; i<=a; i++){
v.clear();pi=0;
for(j=1; j<=a; j++){
if(i==j) continue;
pi++;p[pi]=j;
}
jj=1;
for(j=2; j<=pi; j++){
v.clear();
v.push_back(p[j]);v.push_back(p[jj]);v.push_back(i);
Fill(v);
zx=query(v);
v.clear();
v.push_back(p[jj]);v.push_back(p[j]);v.push_back(i);
Fill(v);
xc=query(v);
if(xc>zx){
jj=j;
}
}
e=0;
for(j=1; j<=pi; j++){
if(j==jj) continue;
v.clear();
v.push_back(p[j]);v.push_back(p[jj]);v.push_back(i);
Fill(v);
zx=query(v);
v.clear();
v.push_back(p[jj]);v.push_back(p[j]);v.push_back(i);
Fill(v);
xc=query(v);
//cout<<zx<<" k "<<xc<<endl;
if(zx-xc>e){
e=zx-xc;
}
}
if(e==a-2){
ONE=i;
LAST=p[jj];
break;
}
}
//cout<<"ONE: "<<ONE<<endl;
//
if(a==3){
v.clear();v.push_back(ONE);Fill(v);
zx=query(v);
/*v.clear();v.push_back(ONE);AntiFill(v);
xc=query(v);*/
if(zx==2){
vv.clear();vv.resize(3);vv[ONE-1]=1;vv[v[1]-1]=2;vv[v[2]-1]=3;
}else{
vv.clear();vv.resize(3);vv[ONE-1]=1;vv[v[2]-1]=2;vv[v[1]-1]=3;
}
answer(vv);
return;
}
/* for(i=1; i<=a; i++){
if(i==ONE) continue;
v.clear();pi=0;
for(j=1; j<=a; j++){
if(i==j) continue;
if(j==ONE) continue;
pi++;p[pi]=j;
}
jj=1;
for(j=2; j<=pi; j++){
v.clear();
v.push_back(p[j]);v.push_back(p[jj]);v.push_back(i);
Fill(v);
zx=query(v);
v.clear();
v.push_back(p[jj]);v.push_back(p[j]);v.push_back(i);
Fill(v);
xc=query(v);
if(xc>zx){
jj=j;
}
}
e=0;
for(j=1; j<=pi; j++){
if(j==jj) continue;
v.clear();
v.push_back(p[j]);v.push_back(p[jj]);v.push_back(i);
Fill(v);
zx=query(v);
v.clear();
v.push_back(p[jj]);v.push_back(p[j]);v.push_back(i);
Fill(v);
xc=query(v);
if(zx-xc>e){
e=zx-xc;
}
}
if(e==a-3){
LAST=i;
break;
}
}*/
//cout<<"LAST: "<<LAST<<endl;
ans.resize(a);
vv.clear();vv.push_back(ONE);vv.push_back(LAST);Fill(vv);
for(i=2; i<a; i++){
v.clear();v.push_back(ONE);v.push_back(LAST);v.push_back(vv[i]);Fill(v);
zx=query(v);
v.clear();v.push_back(LAST);v.push_back(ONE);v.push_back(vv[i]);Fill(v);
xc=query(v);
c=(a+1)-(zx-xc);c/=2;
ans[vv[i]-1]=c;
}
ans[ONE-1]=1;ans[LAST-1]=a;
answer(ans);
}
//
/*int FA[1009];
int query(vector <int> V){
int qw=0;
for(int h=1; h<V.size(); h++){
qw+=abs(FA[V[h]]-FA[V[h-1]]);
}
return qw;
}
void answer(vector <int> P){
for(int h=0; h<P.size(); h++){
cout<<P[h]<<" ";
}
}
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>a;
for(i=1; i<=a; i++){
cin>>c;
FA[i]=c;
}
solve(a);
return 0;
}*/
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... |