| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 919282 |
2024-01-31T14:23:32 Z |
phong |
Swap (BOI16_swap) |
C++17 |
|
58 ms |
185172 KB |
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define ll long long
const int nmax = 2e5 + 5, dmax = 2e5 + 5;
const ll oo = 1e18, base = 311;
const int lg = 18, M =2e2 + 5;
const ll mod = 1e9 + 7;
#define pii pair<ll, int>
#define fi first
#define se second
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' ';
using namespace std;
int n, d[nmax];
vector<int> adj[nmax], tmp;
vector<int> dp[nmax][38];
void get(vector<int> &a, vector<int> &b, vector<int> &c){
int i = 1, j = 1;
for(int cur = 0; cur <= lg; ++cur){
int x = __lg(i), y = __lg(j);
while(i <= b.size() && __lg(i) <= cur){
a.push_back(b[i - 1]);
++i;
}
while(j <= c.size() && __lg(j) <= cur){
a.push_back(c[j - 1]);
++j;
}
}
}
void calc(int x, vector<int> &b, vector<int> &c){
tmp.clear();
tmp.push_back(x);
get(tmp, b, c);
}
void ckmin(vector<int> &a, vector<int> &b){
if(a.empty()) a = b;
else{
for(int i = 0; i < a.size(); ++i){
int u = a[i], v = b[i];
if(d[u] > d[v]){
a = b;
return;
}
if(d[u] < d[v]) return;
}
}
}
vector<int> gg;
int L[nmax], R[nmax];
void update(int u){
if(u * 2 > n){
for(int i = 0; i < adj[u].size(); ++i){
dp[u][i].push_back(adj[u][i]);
}
}
else{
if(u * 2 + 1 > n){
for(int i = 0; i < adj[u * 2].size(); ++i) L[adj[u * 2][i]] = i;
for(int j = 0; j < adj[u].size(); ++j){
int x = adj[u][j];
calc(x, dp[u * 2][L[u * 2]], gg);
ckmin(dp[u][j], tmp);
calc(u * 2,dp[u * 2][L[x]], gg);
ckmin(dp[u][j], tmp);
}
for(int i = 0; i < adj[u * 2].size(); ++i){
dp[u][i].clear();
}
}
else{
for(int i = 0; i < adj[u * 2].size(); ++i) L[adj[u * 2][i]] = i;
for(int i = 0; i < adj[u * 2 + 1].size(); ++i) R[adj[u * 2 + 1][i]] = i;
for(int j = 0; j < adj[u].size(); ++j){
int x = adj[u][j];
calc(x, dp[u * 2][L[u * 2]], dp[u * 2 + 1][R[u * 2 + 1]]);
ckmin(dp[u][j], tmp);
calc(u * 2, dp[u * 2][L[x]], dp[u * 2 + 1][R[u * 2 + 1]]);
ckmin(dp[u][j], tmp);
calc(u * 2 + 1, dp[u * 2][L[x]], dp[u * 2 + 1][R[u * 2]]);
ckmin(dp[u][j], tmp);
calc(u * 2 + 1, dp[u * 2][L[u * 2]], dp[u * 2 + 1][R[x]]);
ckmin(dp[u][j], tmp);
// cout << u << ' ' << x << " # ";
// for(auto p : dp[u][j]) cout << p << ' ';
// cout << "\n";
}
for(int i = 0; i < adj[u * 2].size(); ++i) dp[u * 2][i].clear();
for(int i = 0; i < adj[u * 2 + 1].size(); ++i) dp[u * 2 + 1][i].clear();
}
}
}
main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("code.inp", "r", stdin);
// freopen("code.out", "w", stdout);
cin >> n;
for(int i = 1; i <= n; ++i) cin >> d[i];
for(int i = n; i >= 1; --i){
// adj[i].push_back(i);
int u = i;
while(u > 0){
if(u - 1 > 0 && u % 2 == 1) adj[i].push_back(u - 1);
adj[i].push_back(u);
u /= 2;
}
// cout << i << '#';
// for(auto p : adj[i])cout << p << ' ';
// cout << "\n";
}
for(int i = n; i >= 1; --i) update(i);
// for(int i )
for(auto p : dp[1][0]) cout << d[p] << ' ';
}
/*
5 2
3 2
2 5
3 4
3 1
*/
Compilation message
swap.cpp: In function 'void get(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
swap.cpp:24:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | while(i <= b.size() && __lg(i) <= cur){
| ~~^~~~~~~~~~~
swap.cpp:28:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | while(j <= c.size() && __lg(j) <= cur){
| ~~^~~~~~~~~~~
swap.cpp:23:13: warning: unused variable 'x' [-Wunused-variable]
23 | int x = __lg(i), y = __lg(j);
| ^
swap.cpp:23:26: warning: unused variable 'y' [-Wunused-variable]
23 | int x = __lg(i), y = __lg(j);
| ^
swap.cpp: In function 'void ckmin(std::vector<int>&, std::vector<int>&)':
swap.cpp:42:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(int i = 0; i < a.size(); ++i){
| ~~^~~~~~~~~~
swap.cpp: In function 'void update(int)':
swap.cpp:57:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for(int i = 0; i < adj[u].size(); ++i){
| ~~^~~~~~~~~~~~~~~
swap.cpp:63:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int i = 0; i < adj[u * 2].size(); ++i) L[adj[u * 2][i]] = i;
| ~~^~~~~~~~~~~~~~~~~~~
swap.cpp:64:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for(int j = 0; j < adj[u].size(); ++j){
| ~~^~~~~~~~~~~~~~~
swap.cpp:71:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(int i = 0; i < adj[u * 2].size(); ++i){
| ~~^~~~~~~~~~~~~~~~~~~
swap.cpp:76:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(int i = 0; i < adj[u * 2].size(); ++i) L[adj[u * 2][i]] = i;
| ~~^~~~~~~~~~~~~~~~~~~
swap.cpp:77:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int i = 0; i < adj[u * 2 + 1].size(); ++i) R[adj[u * 2 + 1][i]] = i;
| ~~^~~~~~~~~~~~~~~~~~~~~~~
swap.cpp:78:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int j = 0; j < adj[u].size(); ++j){
| ~~^~~~~~~~~~~~~~~
swap.cpp:95:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for(int i = 0; i < adj[u * 2].size(); ++i) dp[u * 2][i].clear();
| ~~^~~~~~~~~~~~~~~~~~~
swap.cpp:96:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(int i = 0; i < adj[u * 2 + 1].size(); ++i) dp[u * 2 + 1][i].clear();
| ~~^~~~~~~~~~~~~~~~~~~~~~~
swap.cpp: At global scope:
swap.cpp:102:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
102 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
58 ms |
185172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
58 ms |
185172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
58 ms |
185172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
58 ms |
185172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
58 ms |
185172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
