| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 646206 |
2022-09-29T07:42:26 Z |
fatemetmhr |
Swap (BOI16_swap) |
C++17 |
|
13 ms |
21460 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) x.begin(), x.end()
#define pb push_back
#define fi first
#define se second
const int maxn5 = 3e5 + 10;
int n;
vector <int> av[maxn5], tochil[maxn5], ans[maxn5];
int a[maxn5];
void solve(int v){
if(v * 2 + 1 > n){
if(v * 2 > n){
av[v].pb(n + 1);
ans[v].pb(0);
return;
}
solve(v * 2);
int i = 0;
while(av[v * 2][i] < a[v * 2]){
av[v].pb(av[v * 2][i]);
ans[v].pb(0);
tochil[v].pb(0);
i++;
}
ans[v].pb(0);
tochil[v].pb(0);
av[v].pb(a[v * 2]);
while(i < av[v * 2].size()){
ans[v].pb(ans[v * 2][i] + 1);
tochil[v].pb(1);
av[v].pb(av[v * 2][i++]);
}
return;
}
solve(v * 2); solve(v * 2 + 1);
int id1 = 0, id2 = 0;
int re = 0;
while(id1 < av[v * 2].size() || id2 < av[v * 2 + 1].size()){
if(id1 < av[v * 2].size() && (id2 == av[v * 2 + 1].size() || av[v * 2][id1] < av[v * 2 + 1][id2]))
av[v].pb(av[v * 2][id1++]);
else
av[v].pb(av[v * 2 + 1][id2++]);
if(re == 0 && av[v].back() > min(a[v * 2], a[v * 2 + 1])){
re = 1;
int tmp = av[v].back();
av[v][av[v].size() - 1] = min(a[v * 2], a[v * 2 + 1]);
av[v].pb(tmp);
}
if(re == 1 && av[v].back() > max(a[v * 2], a[v * 2 + 1])){
re = 2;
int tmp = av[v].back();
av[v][av[v].size() - 1] = max(a[v * 2], a[v * 2 + 1]);
av[v].pb(tmp);
}
}
av[v].pop_back();
int pt32 = upper_bound(all(av[v * 2 + 1]), a[v * 2]) - av[v * 2 + 1].begin();
int pt33 = upper_bound(all(av[v * 2 + 1]), a[v * 2 + 1]) - av[v * 2 + 1].begin();
int pt22 = upper_bound(all(av[v * 2]), a[v * 2]) - av[v * 2].begin();
id1 = 0; id2 = 0;
for(int i = 0; i < av[v].size(); i++){
while(av[v * 2][id1] < av[v][i])
id1++;
while(av[v * 2 + 1][id2] < av[v][i])
id2++;
int val1 = av[v][i] - 1, val2 = a[v * 2], val3 = a[v * 2 + 1];
if(val1 < min(val2, val3)){
ans[v].pb(0);
tochil[v].pb(0);
}
if(val2 < min(val1, val3)){
ans[v].pb(ans[v * 2][id1] + 1);
tochil[v].pb(1);
}
if(val3 < min(val1, val2)){
if(val1 < val2){
if(ans[v * 2][id1] <= ans[v * 2 + 1][id2]){
ans[v].pb(ans[v * 2][id1] + 1);
tochil[v].pb(3);
}
else{
ans[v].pb(ans[v * 2 + 1][id2] + 1);
tochil[v].pb(2);
}
}
else{
if(ans[v * 2][pt22] <= ans[v * 2 + 1][pt32]){
ans[v].pb(ans[v * 2 + 1][id2] + 1);
tochil[v].pb(2);
}
else{
ans[v].pb(ans[v * 2][id1] + 1);
tochil[v].pb(3);
}
}
}
//cout << "check out " << v << ' ' << i << ' ' << tochil[v].size() << ' ' << val1 << ' ' << val2 << ' ' << val3 << endl;
}
return;
}
void find_ans(int v){
if(v * 2 > n)
return;
int pt = upper_bound(all(av[v]), a[v]) - av[v].begin();
//cout << "aha " << v << ' ' << av[v].size() << ' ' << tochil[v].size() << ' ' << a[v] << ' ' << pt << endl;
if(tochil[v][pt] == 1)
swap(a[v], a[v * 2]);
if(tochil[v][pt] == 2)
swap(a[v], a[v * 2 + 1]);
if(tochil[v][pt] == 3){
swap(a[v], a[v * 2]);
swap(a[v], a[v * 2 + 1]);
}
find_ans(v * 2);
if(v * 2 + 1 <= n)
find_ans(v * 2 + 1);
return;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
solve(1);
find_ans(1);
for(int i = 1; i <= n; i++)
cout << a[i] << ' ';
cout << endl;
}
Compilation message
swap.cpp: In function 'void solve(int)':
swap.cpp:36:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | while(i < av[v * 2].size()){
| ~~^~~~~~~~~~~~~~~~~~
swap.cpp:46:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | while(id1 < av[v * 2].size() || id2 < av[v * 2 + 1].size()){
| ~~~~^~~~~~~~~~~~~~~~~~
swap.cpp:46:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | while(id1 < av[v * 2].size() || id2 < av[v * 2 + 1].size()){
| ~~~~^~~~~~~~~~~~~~~~~~~~~~
swap.cpp:47:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | if(id1 < av[v * 2].size() && (id2 == av[v * 2 + 1].size() || av[v * 2][id1] < av[v * 2 + 1][id2]))
| ~~~~^~~~~~~~~~~~~~~~~~
swap.cpp:47:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | if(id1 < av[v * 2].size() && (id2 == av[v * 2 + 1].size() || av[v * 2][id1] < av[v * 2 + 1][id2]))
| ~~~~^~~~~~~~~~~~~~~~~~~~~~~
swap.cpp:69:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(int i = 0; i < av[v].size(); i++){
| ~~^~~~~~~~~~~~~~
swap.cpp:66:9: warning: unused variable 'pt33' [-Wunused-variable]
66 | int pt33 = upper_bound(all(av[v * 2 + 1]), a[v * 2 + 1]) - av[v * 2 + 1].begin();
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
21460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
21460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
21460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
21460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
21460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
