Submission #1108257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108257		lighton	Swap (BOI16_swap)	C++17	68 / 100	482 ms	262144 KiB

swap

#include<bits/stdc++.h>
#define pb push_back
#define all(v) v.begin(),v.end()
#define forf(i,s,e) for(int i = s; i<=e; i++)
#define forb(i,s,e) for(int i = s; i>=e; i--)
#define idx(i,v) lower_bound(all(v),i)-v.begin()
#define comp(v) v.erase(unique(all(v)),v.end())
#define sz(v) (int)v.size()
#define fs first
#define se second
#define SP << " " <<
#define LN << "\n"
#define IO cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
#pragma GCC optimize("O3,Ofast,unroll-loops")
using namespace std;
typedef long long ll;
ll inf = 1e18;
int N;
int P[200001];
bool small(vector<int> &a, vector<int> &b){
    int ind = 0;
    while(ind < a.size() && ind < b.size() && a[ind]==b[ind]) ind++;
    if(ind == a.size() && ind == b.size()) return true;
    else return a[ind]<b[ind];
}
void merg(vector<int> &a, vector<int> &b, int r, vector<int> &ret){
    ret.resize(sz(a)+sz(b),0);
    ret[1] = r;
    int dep = 1;
    forf(i,2,sz(ret)-1){
        if(1<<(dep+1) == i) dep++;
        if(i&(1<<(dep-1))) ret[i] = b[i^(1<<dep)];
        else ret[i] = a[i^(1<<dep)^(1<<(dep-1))];
    }
}
unordered_map<int, vector<int> > dp[200001];
void dfs(int now, vector<int> p){
    if(1<=now && now<=N) p.pb(P[now]);
    if(1<=(now^1) && (now^1)<=N) p.pb(P[now^1]);
    int l = now*2, r=now*2+1;
    if(r<=N) dfs(l,p), dfs(r,p);
    for(auto v: p){
        if(l > N) dp[now][v] = {0,v};
        else if(r > N) dp[now][v] = {0,min(P[l],v),max(P[l],v)};
        else{
            if(v < P[l] && v < P[r]) merg(dp[l][P[l]],dp[r][P[r]],v,dp[now][v]);
            else if(P[l] < v && P[l] < P[r]) merg(dp[l][v],dp[r][P[r]],P[l],dp[now][v]);
            else{
                vector<int> v1,v2;
                merg(dp[l][v],dp[r][P[l]],P[r],v1);
                merg(dp[l][P[l]],dp[r][v],P[r],v2);
                if(small(v1,v2)) dp[now][v] = v1;
                else dp[now][v] = v2;
            }
        }
    }
}
int main(){
    IO
    cin>>N; forf(i,1,N) cin>>P[i];
    dfs(1,{});
    forf(i,1,sz(dp[1][P[1]])-1) cout<<dp[1][P[1]][i]<<" ";
}

Compilation message (stderr)

swap.cpp: In function 'bool small(std::vector<int>&, std::vector<int>&)':
swap.cpp:22:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     while(ind < a.size() && ind < b.size() && a[ind]==b[ind]) ind++;
      |           ~~~~^~~~~~~~~~
swap.cpp:22:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     while(ind < a.size() && ind < b.size() && a[ind]==b[ind]) ind++;
      |                             ~~~~^~~~~~~~~~
swap.cpp:23:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     if(ind == a.size() && ind == b.size()) return true;
      |        ~~~~^~~~~~~~~~~
swap.cpp:23:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     if(ind == a.size() && ind == b.size()) return true;
      |                           ~~~~^~~~~~~~~~~

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