| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1146741 | Rawlat_vanak | Art Collections (BOI22_art) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "art.h"
using namespace std;
#define int long long
#define speedIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//#define mod 1000000007
#define f first
#define s second
#define pii pair<int,int>
#define pb push_back
vector<int> bit,counted;
void update(int idx, int val){
while(idx<bit.size()){
bit[idx]+=val;
idx+=(idx&(-idx));
}
}
int get(int idx){
int ans=0;
while(idx>0){
ans+=bit[idx];
idx-=(idx&(-idx));
}
return ans;
}
void solve(int n){
vector<int> r(n),tmp(n),ans(n);
for(int i=0;i<n;i++){
r[i]=i+1;
}
int initial=publish(r);
//vector<bool> counted(n+1,false);
counted.resize(n+1,0);
bit.resize(n+1,0);
set<int> used;
for(int i=0;i<n-1;i++){
tmp[n-1]=i+1;
for(int j=0;j<n-1;j++){
if(j<i){
tmp[j]=j+1;
}if(j>=i){
tmp[j]=j+2;
}
}
int cur=publish(tmp);
int d=cur-initial-i+n;
d/=2;
//cout<<d<<' '<<i<<'\n';
for(int k=n-d;k>=n-d-i;k--){
if(used.empty()){
used.insert(k);
counted[k]=1;
update(k,1);
ans[i]=k;
break;
}
if(counted[k]) continue;
int bigger=i-get(k);
if(bigger==n-d-k){
counted[k]=1;
ans[i]=k;
update(k,1);
used.insert(k);
break;
}
}
}
for(int i=1;i<=n;i++){
if(!counted[i]){
ans[n-1]=i;
break;
}
}
//answer(ans);
vector<int> realans(n);
for(int i=0;i<n;i++){
realans[ans[i]-1]=i+1;
}
answer(realans);
}