oj.uz

Submission #919285

# Submission time Handle Problem Language Result Execution time Memory
919285 2024-01-31T14:26:06 Z phong Swap (BOI16_swap) C++17
48 / 100
 84 ms 262144 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][50];
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 * 2][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(){
      | ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 241232 KB Output is correct
2 Correct 72 ms 241232 KB Output is correct
3 Correct 73 ms 241376 KB Output is correct
4 Correct 72 ms 241232 KB Output is correct
5 Correct 73 ms 241232 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 241232 KB Output is correct
2 Correct 72 ms 241232 KB Output is correct
3 Correct 73 ms 241376 KB Output is correct
4 Correct 72 ms 241232 KB Output is correct
5 Correct 73 ms 241232 KB Output is correct
6 Correct 73 ms 241232 KB Output is correct
7 Correct 72 ms 241376 KB Output is correct
8 Correct 72 ms 241232 KB Output is correct
9 Correct 74 ms 241184 KB Output is correct
10 Correct 73 ms 241156 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 241232 KB Output is correct
2 Correct 72 ms 241232 KB Output is correct
3 Correct 73 ms 241376 KB Output is correct
4 Correct 72 ms 241232 KB Output is correct
5 Correct 73 ms 241232 KB Output is correct
6 Correct 73 ms 241232 KB Output is correct
7 Correct 72 ms 241376 KB Output is correct
8 Correct 72 ms 241232 KB Output is correct
9 Correct 74 ms 241184 KB Output is correct
10 Correct 73 ms 241156 KB Output is correct
11 Correct 76 ms 242000 KB Output is correct
12 Correct 76 ms 242024 KB Output is correct
13 Correct 77 ms 242028 KB Output is correct
14 Correct 74 ms 242000 KB Output is correct
15 Correct 75 ms 242004 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 241232 KB Output is correct
2 Correct 72 ms 241232 KB Output is correct
3 Correct 73 ms 241376 KB Output is correct
4 Correct 72 ms 241232 KB Output is correct
5 Correct 73 ms 241232 KB Output is correct
6 Correct 73 ms 241232 KB Output is correct
7 Correct 72 ms 241376 KB Output is correct
8 Correct 72 ms 241232 KB Output is correct
9 Correct 74 ms 241184 KB Output is correct
10 Correct 73 ms 241156 KB Output is correct
11 Correct 76 ms 242000 KB Output is correct
12 Correct 76 ms 242024 KB Output is correct
13 Correct 77 ms 242028 KB Output is correct
14 Correct 74 ms 242000 KB Output is correct
15 Correct 75 ms 242004 KB Output is correct
16 Runtime error 84 ms 262144 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 241232 KB Output is correct
2 Correct 72 ms 241232 KB Output is correct
3 Correct 73 ms 241376 KB Output is correct
4 Correct 72 ms 241232 KB Output is correct
5 Correct 73 ms 241232 KB Output is correct
6 Correct 73 ms 241232 KB Output is correct
7 Correct 72 ms 241376 KB Output is correct
8 Correct 72 ms 241232 KB Output is correct
9 Correct 74 ms 241184 KB Output is correct
10 Correct 73 ms 241156 KB Output is correct
11 Correct 76 ms 242000 KB Output is correct
12 Correct 76 ms 242024 KB Output is correct
13 Correct 77 ms 242028 KB Output is correct
14 Correct 74 ms 242000 KB Output is correct
15 Correct 75 ms 242004 KB Output is correct
16 Runtime error 84 ms 262144 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -