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"
using namespace std;
//
// --- Sample implementation for the task art ---
//
// To compile this program with the sample grader, place:
// art.h art_sample.cpp sample_grader.cpp
// in a single folder, then open the terminal in this directory (right-click onto an empty spot in the directory,
// left click on "Open in terminal") and enter e.g.:
// g++ -std=c++17 art_sample.cpp sample_grader.cpp
// in this folder. This will create a file a.out in the current directory which you can execute from the terminal
// as ./a.out
// See task statement or sample_grader.cpp for the input specification
//
const int MAX_N = 1e4 + 5;
int fenwick[MAX_N], position[MAX_N];
void add(int x, int v) {
for(int i = x; i < MAX_N; i += (i & -i)) {
fenwick[i] += v;
}
}
int get(int x) {
int res = 0;
for(int i = x; i >= 1; i -= (i & -i)) {
res += fenwick[i];
}
return res;
}
void solve(int N) {
int inversion, new_inversion, between, l, r, mid, pos;
vector <int> order(N);
for(int i = 1; i < MAX_N; i++) {
fenwick[i] = i & -i;
}
iota(order.begin(), order.end(), 1);
inversion = publish(order);
position[1] = MAX_N / 2;
add(MAX_N / 2, -1);
for(int i = N - 1; i >= 1; i--) {
swap(order[0], order[i]);
new_inversion = publish(order);
between = (abs(new_inversion - inversion) - 1) / 2 + 1;
if(inversion > new_inversion) {
l = 1, r = position[order[i]] - 1;
while(l <= r) {
mid = (l + r) / 2;
if(get(position[order[i]] - 1) - get(mid - 1) >= between) {
l = mid + 1;
pos = mid;
}
else {
r = mid - 1;
}
}
}
else {
l = position[order[i]] + 1, r = MAX_N - 1;
while(l <= r) {
mid = (l + r) / 2;
if(get(mid) - get(position[order[i]]) >= between) {
pos = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
}
}
position[order[0]] = pos;
add(pos, -1);
inversion = new_inversion;
}
int min_value = MAX_N;
for(int i = 1; i <= N; i++) {
min_value = min(min_value, position[i]);
}
for(int i = 1; i <= N; i++) {
position[i] -= min_value - 1;
}
vector <int> ans;
for(int i = 1; i <= N; i++) {
ans.push_back(position[i]);
}
answer(ans);
}
Compilation message (stderr)
art.cpp: In function 'void solve(int)':
art.cpp:83:28: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
83 | position[order[0]] = pos;
| ~~~~~~~~~~~~~~~~~~~^~~~~
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... |