이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
const int INF = 1000000000;
using namespace std;
typedef long long ll;
int Data[1<<19];
int pows[19];
void init(int N){
fill(Data+1, Data+N+1, 1);
int p = 1<<18;
pows[0] = 0;
for(int i = 1; i <= 18; i++){
pows[i] = pows[i-1] + p;
p/= 2;
}
for(int i = 1; i <= 18; i++){
for(int j = 0; j < 1<<(18-i); j++){
Data[pows[i] + j] = Data[pows[i-1] + j*2] + Data[pows[i-1] + j*2 + 1];
}
}
}
void remove(int index){
int id = index;
Data[id] = 0;
for(int i = 1; i <= 18; i++){
id /= 2;
Data[pows[i] + id]--;
}
}
int sum(int i1, int i2, int level = 0){
if(i1 > i2) return 0;
if(i1 == i2){
return Data[pows[level] + i1];
}
int res = 0;
if(i1 % 2 == 1){
res += Data[pows[level] + i1];
i1++;
}
if(i2 % 2 == 0){
res += Data[pows[level] + i2];
i2--;
}
return res + sum(i1/2, i2/2, level+1);
}
int getMin(){
int ind = 0;
int lvl = 18;
while(lvl > 0){
lvl--;
if(Data[pows[lvl]+2*ind]){
ind *= 2;
} else {
ind = 2*ind + 1;
}
}
return ind;
}
int getMax(){
int ind = 0;
int lvl = 18;
while(lvl > 0){
lvl--;
if(Data[pows[lvl]+2*ind+1]){
ind = 2*ind + 1;
} else {
ind = 2*ind;
}
}
return ind;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int N;
cin >> N;
init(2*N-1);
vector<int> result;
int a;
cin >> a;
remove(a);
result.push_back(a);
for(int i = 1; i < N; i++){
cin >> a;
int x1 = sum(1,a-1);
int x2 = sum(a+1,N);
if(!Data[a]){
if(x1 == x2){
int y = getMax();
result.push_back(y);
remove(y);
y = getMin();
result.push_back(y);
remove(y);
} else if(x1 < x2){
int y = getMin();
result.push_back(y);
remove(y);
y = getMin();
result.push_back(y);
remove(y);
} else {
int y = getMax();
result.push_back(y);
remove(y);
y = getMax();
result.push_back(y);
remove(y);
}
}else{
result.push_back(a);
remove(a);
if(x1 > x2){
int y = getMax();
result.push_back(y);
remove(y);
} else {
int y = getMin();
result.push_back(y);
remove(y);
}
}
}
for(auto k : result) cout << k << ' ';
cout << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |