This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#ifndef LOCAL
#include "art.h"
#endif
#include <bits/stdc++.h>
using namespace std;
int n, now, lst;
vector<int> v;
bool compare(int a, int b){
if(a == b) return false;
int pa = find(v.begin(), v.end(), a) - v.begin();
int pb = find(v.begin(), v.end(), b) - v.begin();
swap(v[pa], v[pb]);
lst = publish(v);
swap(v[pa], v[pb]);
if(pa < pb) return now < lst;
return now > lst;
}
int p(int x){ return (x - 1) / 2; }
int l(int x){ return x * 2 + 1; }
int r(int x){ return x * 2 + 2; }
void heapify(int t, int sz){
while(l(t) < sz){
if(r(t) < sz && compare(v[l(t)], v[r(t)]) && compare(v[t], v[r(t)])){
swap(v[t], v[r(t)]); now = lst; t = r(t);
}
else if(compare(v[t], v[l(t)])){
swap(v[t], v[l(t)]); now = lst; t = l(t);
}
else break;
}
}
void make_heap(){
for(int i=n-1; i; i--){
if(compare(v[i], v[p(i)])) continue;
swap(v[i], v[p(i)]); now = lst;
heapify(i, n);
}
}
void heap_sort(){
make_heap();
int sz = n;
while(sz > 1){
swap(v[0], v[--sz]); now = publish(v);
if(sz > 1) heapify(0, sz);
}
}
void solve(int _n){
n = _n; v.resize(n);
iota(v.begin(), v.end(), 1);
now = publish(v);
heap_sort();
answer(v);
}
Compilation message (stderr)
interface.cpp: In function 'int publish(std::vector<int>)':
interface.cpp:20:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
20 | if(v.size() != N) {
| ~~~~~~~~~^~~~
interface.cpp: In function 'void answer(std::vector<int>)':
interface.cpp:36:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
36 | if(v.size() != N) {
| ~~~~~~~~~^~~~
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |