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>
using namespace std;
#define rep(i,a,b) for(int i = (a); i < (b); i++)
typedef long long ll;
#define pb push_back
typedef pair<int, int> pii;
int INF = 3e5;
int n;
// graph
vector<bool> edges_up;
vector<bool> edges_down;
vector<int> start;
vector<int> when_ind_fixed;
vector<int> eend;
vector<int> calcs;
bool calc(int node)
{
//cerr << node << "\n";
if (when_ind_fixed[node] == INF) return true;
int left = node * 2;
if (left < n + 1) {
// cerr << "left " << left << "\n";
// cerr << "ed_do " << edges_down[left] << "\n";
// cerr << "fix " << when_ind_fixed[node] << "\n";
if (edges_up[left] && when_ind_fixed[node] >= left) {
//cerr << "pbl\n";
calcs.pb(left);
}
}
int right = (node * 2) + 1;
if (right < n + 1) {
if (edges_up[right] && when_ind_fixed[node] >= right) {
//cerr << "pbr\n";
calcs.pb(right);
}
}
return false;
}
int32_t main()
{
// fast
cin >> n;
start.assign(n + 1, -1);
int a;
rep(i,1,n + 1){
cin >> a;
start[a] = i;
}
when_ind_fixed.assign(n + 1, INF);
edges_up.assign(n + 1, true);
edges_down.assign(n + 1, true);
eend.assign(n + 1, -1);
// .
rep(i,1,n + 1) // n ?
{
//cerr << "REP " << i << " !!!\n";
int oth_min = INF;
if (start[i] != 1)
{
int other;
if (((start[i]/2)*2)+1 != start[i]) other = ((start[i]/2)*2)+1;
else other = ((start[i]/2)*2);
//cerr << "other " << other << "\n";
if (when_ind_fixed[start[i]/2] == INF && edges_down[start[i]]) {
when_ind_fixed[start[i]/2] = start[i];
edges_down[start[i]] = false;
eend[start[i]/2] = i;
continue;
}
else if (other < n + 1) {
// when_ind_fixed[start[i]/2] >= max(start[i], other) -> true , hm 0 , hm start[i] / 2
if (edges_down[start[i]] && edges_up[other] && when_ind_fixed[start[i]/2] >= max(start[i], other)) {
calcs = {};
calcs.pb(other);
int j = 0;
while (j < calcs.size()) {
// j < n
if (calc(calcs[j])) {
oth_min = calcs[j];
break;
}
else j++;
}
}
}
}
int here_min = INF;
calcs = {};
calcs.pb(start[i]);
int j = 0;
while (j < calcs.size()) {
if (calc(calcs[j])) {
here_min = calcs[j];
break;
}
else j++;
}
assert(!(here_min == INF && oth_min == INF));
if (oth_min < here_min)
{
edges_down[start[i]] = false;
//
eend[oth_min] = i;
when_ind_fixed[oth_min] = oth_min;
int stop = start[i]/2;
int j = oth_min;
while (j != stop)
{
//assert(j > stop);
edges_up[j] = false;
j = j / 2;
}
}
else
{
eend[here_min] = i;
when_ind_fixed[here_min] = here_min;
if (here_min == start[i]) when_ind_fixed[here_min] = 0;
// edges_down[here_min] = false; // hm
int stop = start[i];
int j = here_min;
while (j != stop)
{
//assert(j > stop);
edges_up[j] = false;
j = j / 2;
}
}
// min oth_min, here_min , node / 2 rec edges, when_ind node
// eend[] = i;
}
rep(i, 1, n + 1){
cout << eend[i] << " ";
}
cout << "\n";
}
Compilation message (stderr)
swap.cpp: In function 'int32_t main()':
swap.cpp:102:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | while (j < calcs.size()) {
| ~~^~~~~~~~~~~~~~
swap.cpp:120:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | while (j < calcs.size()) {
| ~~^~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |