Submission #919305

#TimeUsernameProblemLanguageResultExecution timeMemory
919305thanh913Swap (BOI16_swap)C++14
68 / 100
1043 ms190324 KiB
//test code #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<vector<int>> dp[nmax]; void get(vector<int> &a, vector<int> &b, vector<int> &c){ a.reserve(b.size() + c.size()); 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){ dp[u].resize(adj[u].size() + 1); 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); } dp[u * 2].clear(); adj[u * 2].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"; } dp[u * 2].clear(); adj[u * 2].clear(); dp[u * 2 + 1].clear(); adj[u * 2 + 1].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 (stderr)

swap.cpp: In function 'void get(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
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(i <= b.size() && __lg(i) <= cur){
      |               ~~^~~~~~~~~~~
swap.cpp:32:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         while(j <= c.size() && __lg(j) <= cur){
      |               ~~^~~~~~~~~~~
swap.cpp:27:13: warning: unused variable 'x' [-Wunused-variable]
   27 |         int x = __lg(i), y = __lg(j);
      |             ^
swap.cpp:27:26: warning: unused variable 'y' [-Wunused-variable]
   27 |         int x = __lg(i), y = __lg(j);
      |                          ^
swap.cpp: In function 'void ckmin(std::vector<int>&, std::vector<int>&)':
swap.cpp:46:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(int i = 0; i < a.size(); ++i){
      |                        ~~^~~~~~~~~~
swap.cpp: In function 'void update(int)':
swap.cpp:63:26: 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].size(); ++i){
      |                        ~~^~~~~~~~~~~~~~~
swap.cpp:70:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |             for(int i = 0; i < adj[u * 2].size(); ++i) L[adj[u * 2][i]] = i;
      |                            ~~^~~~~~~~~~~~~~~~~~~
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 j = 0; j < adj[u].size(); ++j){
      |                            ~~^~~~~~~~~~~~~~~
swap.cpp:82:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |             for(int i = 0; i < adj[u * 2].size(); ++i) L[adj[u * 2][i]] = i;
      |                            ~~^~~~~~~~~~~~~~~~~~~
swap.cpp:83:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |             for(int i = 0; i < adj[u * 2 + 1].size(); ++i) R[adj[u * 2 + 1][i]] = i;
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~~
swap.cpp:84:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |             for(int j = 0; j < adj[u].size(); ++j){
      |                            ~~^~~~~~~~~~~~~~~
swap.cpp: At global scope:
swap.cpp:107:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  107 | main(){
      | ^~~~
#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...