Submission #646211

#TimeUsernameProblemLanguageResultExecution timeMemory
646211fatemetmhrSwap (BOI16_swap)C++17
100 / 100
245 ms75752 KiB
#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(i > 0 && val1 == av[v][i - 1]){ ans[v].pb(-1); tochil[v].pb(-1); continue; } 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 (stderr)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...