# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1062116 | new_acc | 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<bits/stdc++.h>
//#include "art.h"
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e6+10;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e13;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=20;
int t[N];
int que(vi x){
return publish(x);
}
void solve(int n){
vi pom;
for(int i=1;i<=n;i++) pom.push_back(i);
int base=que(pom),curr=0;
for(int i=1;i<n;i++){
vi xd=pom;
int wsk=n;
for(int k=i;k<n;k++) xd[i]=wsk--;
int val=que(xd)-curr,val2=base-curr;
int val3=val+val2-((n-i)*(n-i-1)>>1);
val3>>=1;
t[i]=val3;
curr+=val3;
}
vi sorted;
sorted.push_back(n);
for(int i=n-1;i>=1;i--){
vi s2;
for(int k=0;k<=t[i];k++) s2.push_back(sorted[k]);
s2.push_back(i);
for(int k=t[i]+1;k<sorted.size();k++) s2.push_back(sorted[k]);
sorted=s2;
}
answer(sorted);
}