제출 #919396

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
919396		phong	Swap (BOI16_swap)	C++17	68 / 100	1018 ms	209132 KiB

swap

#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;
const ll oo = 1e18, base = 311;
const int lg = 38, 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){
    for(int i = 1, j = 1, l = 1, pos; i <= b.size() || j <= c.size(); i += l, j += l, l <<= 1){
        for(pos = i; pos <= b.size() && pos <= i + l - 1; ++pos) a.push_back(b[pos - 1]);
        for(pos = j; pos <= c.size() && pos <= j + l - 1; ++pos) a.push_back(c[pos - 1]);

    }
}
void calc(int x,  vector<int> &b, vector<int> &c){
    tmp ={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];
bool f[nmax][lg + 1];
void update(int u){
    dp[u].resize(adj[u].size());

    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 << 1].size(); ++i) L[adj[u << 1][i]] = i;
            for(int j = 0; j < adj[u].size(); ++j){
//                if(!f[u][j]) continue;
                int x = adj[u][j];
                int rs = min(d[x], d[u << 1]);
                if(rs == d[x]){
                    calc(x, dp[u << 1][L[u << 1]], gg);
                    ckmin(dp[u][j], tmp);
                }
                else {
                    calc(u << 1,dp[u << 1][L[x]], gg);
                    ckmin(dp[u][j], tmp);
                }
            }
            dp[u << 1].clear();
            adj[u << 1].clear();
        }
        else{
            for(int i = 0; i < adj[u << 1].size(); ++i) L[adj[u << 1][i]] = i;
            for(int i = 0; i < adj[u << 1 | 1].size(); ++i) R[adj[u << 1 | 1][i]] = i;
            for(int j = 0; j < adj[u].size(); ++j){
//                if(!f[u][j]) continue;
                int x = adj[u][j];
                int rs = min({d[x], d[u << 1], d[u << 1 | 1]});
                if(rs == d[x]){
                    calc(x, dp[u << 1][L[u * 2]], dp[u << 1 | 1][R[u << 1 | 1]]);
                    ckmin(dp[u][j], tmp);
                }
                else if(rs == d[u << 1]){
                    calc(u << 1, dp[u << 1][L[x]], dp[u << 1 | 1][R[u << 1 | 1]]);
                    ckmin(dp[u][j], tmp);
                }
                else{
                    calc(u << 1 | 1, dp[u << 1][L[x]], dp[u << 1 | 1][R[u * 2]]);
                    ckmin(dp[u][j], tmp);
                    calc(u << 1 | 1, dp[u << 1][L[u * 2]], dp[u << 1 | 1][R[x]]);
                    ckmin(dp[u][j], tmp);
                }
//                cout << u << ' ' << x << " # ";
//                for(auto p : dp[u][j]) cout << p << ' ';
//                cout << "\n";
            }
            dp[u << 1].clear();  adj[u << 1].clear();
            dp[u << 1 | 1].clear();  adj[u << 1 | 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];
    f[1][0] = 1;
    for(int i = n; i >= 1; --i){
//        adj[i].push_back(i);
        int u = i, j =0;
//        for(int j = )
//                        int pos = i >> j / 2 ^ j & 1;

        while(u > 0){
            ++j;
            adj[i].push_back(u);
            if(u - 1 > 0 && u % 2 == 1) adj[i].push_back(u - 1);
            u >>= 1;
        }
    //        cout << i << '#';
//        for(auto p : adj[i])cout << p << ' ';
//        cout << "\n";
    }
    for(int i = 1; i * 2 + 1 <= n; ++i){
        for(int j = 0; j < adj[i * 2].size(); ++j) L[adj[i * 2][j]] = j;
        for(int j = 0; j < adj[i * 2 + 1].size(); ++j) R[adj[i * 2 + 1][j]] = j;

        for(int j = 0; j < adj[i].size(); ++j){
            int x = adj[i][j];
            if(f[i][j]){
                int rs = min({d[x], d[i * 2], d[i * 2 + 1]});
                if(rs == d[x]){
                    if(x > 1) f[i * 2][L[x / 2]] = 1;
                    f[i * 2][L[i * 2]] = 1;
                    if(x > 1) f[i * 2 + 1][R[x / 2]] = 1;
                    f[i * 2 + 1][R[i * 2]] = 1;
                }
                else if(rs == d[i * 2]){
                    if(x > 1)f[i * 2][L[x / 2]] = 1;
                    f[i * 2 + 1][R[i * 2 + 1]] = 1;
                }
                else{
                    f[i * 2][L[i * 2]] = f[i * 2 + 1][R[i * 2 + 1]] = 1;
                }
            }
        }
    }
    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

*/

컴파일 시 표준 에러 (stderr) 메시지

swap.cpp: In function 'void get(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
swap.cpp:21:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i = 1, j = 1, l = 1, pos; i <= b.size() || j <= c.size(); i += l, j += l, l <<= 1){
      |                                       ~~^~~~~~~~~~~
swap.cpp:21:58: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i = 1, j = 1, l = 1, pos; i <= b.size() || j <= c.size(); i += l, j += l, l <<= 1){
      |                                                        ~~^~~~~~~~~~~
swap.cpp:22:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for(pos = i; pos <= b.size() && pos <= i + l - 1; ++pos) a.push_back(b[pos - 1]);
      |                      ~~~~^~~~~~~~~~~
swap.cpp:23:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         for(pos = j; pos <= c.size() && pos <= j + l - 1; ++pos) a.push_back(c[pos - 1]);
      |                      ~~~~^~~~~~~~~~~
swap.cpp: In function 'void ckmin(std::vector<int>&, std::vector<int>&)':
swap.cpp:34:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for(int i = 0; i < a.size(); ++i){
      |                        ~~^~~~~~~~~~
swap.cpp: In function 'void update(int)':
swap.cpp:51:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for(int i = 0; i < adj[u].size(); ++i){
      |                        ~~^~~~~~~~~~~~~~~
swap.cpp:57:30: 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 << 1].size(); ++i) L[adj[u << 1][i]] = i;
      |                            ~~^~~~~~~~~~~~~~~~~~~~
swap.cpp:58:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             for(int j = 0; j < adj[u].size(); ++j){
      |                            ~~^~~~~~~~~~~~~~~
swap.cpp:75:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |             for(int i = 0; i < adj[u << 1].size(); ++i) L[adj[u << 1][i]] = 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 << 1 | 1].size(); ++i) R[adj[u << 1 | 1][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 j = 0; j < adj[u].size(); ++j){
      |                            ~~^~~~~~~~~~~~~~~
swap.cpp: At global scope:
swap.cpp:105:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  105 | main(){
      | ^~~~
swap.cpp: In function 'int main()':
swap.cpp:130:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |         for(int j = 0; j < adj[i * 2].size(); ++j) L[adj[i * 2][j]] = j;
      |                        ~~^~~~~~~~~~~~~~~~~~~
swap.cpp:131:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |         for(int j = 0; j < adj[i * 2 + 1].size(); ++j) R[adj[i * 2 + 1][j]] = j;
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~~
swap.cpp:133:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |         for(int j = 0; j < adj[i].size(); ++j){
      |                        ~~^~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 27 / 27
• Subtask 4: 20 / 20
• Subtask 5: 0 / 32