| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 563360 |
2022-05-17T02:57:32 Z |
minhcool |
Swap (BOI16_swap) |
C++17 |
|
101 ms |
262144 KB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 2e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
int n;
int arr[N];
// if initially arr[i] = j, what is the minimum array?
vector<ii> dp[N][75];
map<int, int> mp[N];
vector<ii> merge(vector<ii> a, vector<ii> b){
vector<ii> c;
int itr1 = 0, itr2 = 0;
while(itr1 < a.size() || itr2 < b.size()){
if(itr1 == a.size()){
c.pb(b[itr2]);
itr2++;
}
else if(itr2 == b.size()){
c.pb(a[itr1]);
itr1++;
}
else if(a[itr1].fi < b[itr2].fi){
c.pb(a[itr1]);
itr1++;
}
else{
c.pb(b[itr2]);
itr2++;
}
}
return c;
}
void ins(int i, int j){
if(mp[i].find(j) != mp[i].end()) return;
mp[i][j] = 0;
mp[i][j] = mp[i].size();
}
void process(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> arr[i];
//cout << "OK\n";
//return;
for(int i = 1; i <= n; i++){
int itr = i;
mp[i][arr[i]] = 1;
while(itr != 1){
itr /= 2;
ins(i, arr[itr]);
ins(i, arr[itr << 1]);
ins(i, arr[itr << 1 | 1]);
//if(itr == 1) break;
}
}
//return;
for(int i = n; i >= 1; i--){
if(i * 2 > n){
//for(int j = 1; j <= n; j++) dp[i][j].pb({i, j});
for(auto it : mp[i]) dp[i][it.se].pb({i, it.fi});
}
else if(i * 2 + 1 > n){
for(auto it : mp[i]){
int j = it.fi;
//if(j == arr[i * 2]) continue;
dp[i][it.se].pb({i, min(j, arr[i * 2])});
dp[i][it.se].pb({i * 2, max(j, arr[i * 2])});
}
}
else{//continue;
for(auto it1 : mp[i]){
int ind = it1.se, j = it1.fi;
int temp = min(j, min(arr[i * 2], arr[i * 2 + 1]));
//cout << i << " " << j << " " << temp << "\n";
if(temp == j){// no swapping
int temp1 = mp[i * 2][arr[i * 2]], temp2 = mp[i * 2 + 1][arr[i * 2 + 1]];
vector<ii> temp = merge(dp[i * 2][temp1], dp[i * 2 + 1][temp2]);
dp[i][ind].pb({i, j});
for(auto it : temp) dp[i][ind].pb(it);
}
else if(temp == arr[i * 2]){
//cout << "OK\n";
int temp1 = mp[i * 2 + 1][arr[i * 2 + 1]], temp2 = mp[i * 2][j];
vector<ii> temp = merge(dp[i * 2][temp2], dp[i * 2 + 1][temp1]);
dp[i][ind].pb({i, arr[i * 2]});
for(auto it : temp) dp[i][ind].pb(it);
}
else{
//continue;
int tempo1 = mp[i * 2 + 1][arr[i * 2]], tempo2 = mp[i * 2][arr[i * 2]];
vector<ii> temp1 = merge(dp[i * 2][mp[i * 2][j]], dp[i * 2 + 1][tempo1]), temp2 = merge(dp[i * 2][tempo2], dp[i * 2 + 1][mp[i * 2 + 1][j]]);
dp[i][ind].pb({i, arr[i * 2 + 1]});
bool ck = 0;
assert(temp1.size() == temp2.size());
for(int i = 0; i < temp1.size(); i++){
assert(temp1[i].fi == temp2[i].fi);
if(temp1[i].se != temp2[i].se){
ck = (temp1[i].se < temp2[i].se);
break;
}
}
if(!ck) for(auto it : temp2) dp[i][ind].pb(it);
else for(auto it : temp1) dp[i][ind].pb(it);
}
}
}
for(int j = 1; j <= n; j++){
//cout << i << " " << j << "\n";
//for(auto it : dp[i][j]) cout << it.fi << " " << it.se << "\n";
//cout << "\n";
}
}
for(auto it : dp[1][mp[1][arr[1]]]) cout << it.se << " ";
}
signed main(){
ios_base::sync_with_stdio(0);
process();
}
Compilation message
swap.cpp: In function 'std::vector<std::pair<long long int, long long int> > merge(std::vector<std::pair<long long int, long long int> >, std::vector<std::pair<long long int, long long int> >)':
swap.cpp:26:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | while(itr1 < a.size() || itr2 < b.size()){
| ~~~~~^~~~~~~~~~
swap.cpp:26:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | while(itr1 < a.size() || itr2 < b.size()){
| ~~~~~^~~~~~~~~~
swap.cpp:27:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | if(itr1 == a.size()){
| ~~~~~^~~~~~~~~~~
swap.cpp:31:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | else if(itr2 == b.size()){
| ~~~~~^~~~~~~~~~~
swap.cpp: In function 'void process()':
swap.cpp:108:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(int i = 0; i < temp1.size(); i++){
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
101 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
101 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
101 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
101 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
101 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
