# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
602456 | MrDeboo | Art Collections (BOI22_art) | C++17 | 0 ms | 0 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 "art.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int>vc(4001,-1)
int sbmt(vector<int>vct){
int tot=0,a=0;
vector<int>v;
for(int i=1;i<=n;i++){
if(vc[i]==-1)a++;
else {tot+=a;v.push_back(i);}
}
for(auto &i:vct)v.push_back(i);
return publish(v)-tot;
}
void solve(int N){
n=N;
vector<int>v;
for(int i=1;i<=n;i++)v.push_back(i);
int a=sbmt(v);
while(v.size()>1){
int x=v.back();
vector<int>vc={x};
for(int i=0;i<v.size()-1;i++)vc.push_back(v[i]);
int b=sbmt(vc);
int y=b-a;
vector<int>voc;
for(int i=1;i<=n;i++){
if(vc[i]==-1)voc.push_back(i);
}
int in=-1,g;
for(int i=0;i<voc.size();i++){
if(i-(voc.size()-i-1)==y){
in=voc[i];
g=voc.size()-i-1;
break;
}
}
vc[in]=x;
a-=g;
v.pop_back();
}
vector<bool>bl(n+1);
for(int i=1;i<=n;i++){
if(vc[i]!=-1)bl[vc[i]]=1;
}
int f=0;
for(int i=1;i<=n;i++){
if(!bl[i])f=i;
}
for(int i=1;i<=n;i++){
if(vc[i]==-1)vc[i]=f;
}
vector<int>ans;
for(int i=1;i<=n;i++)ans.push_back(vc[i]);
answer(ans);
}