Submission #1108264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108264		lighton	Swap (BOI16_swap)	C++17	100 / 100	703 ms	8892 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);
using namespace std;
typedef long long ll;
ll inf = 1e18;
int N;
int P[1000001];
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> > dfs(int now, vector<int> p){
    p.pb(P[now]);
    vector<int> lp,rp;
    unordered_map<int,vector<int> > ret;
    int l = now*2, r=now*2+1;
    unordered_map<int, vector<int> > lret,rret;
    int flg = 0;
    for(auto v: p){
        if(l==N && P[l] < v) lp.pb(v);
        else if(r<=N){
            if(P[l] < v && P[l] < P[r]) lp.pb(v);
            else if(P[r] < v && P[r] < P[l]){
                lp.pb(v);
                rp.pb(v);
                flg = 1;
            }
        }
    }
    if(flg) rp.pb(P[l]);

    if(r<=N) lret = dfs(l,lp), rret=dfs(r,rp);
    for(auto v: p){
        if(l > N) ret[v] = {0,v};
        else if(r > N) ret[v] = {0,min(P[l],v),max(P[l],v)};
        else{
            if(v < P[l] && v < P[r]) merg(lret[P[l]],rret[P[r]],v,ret[v]);
            else if(P[l] < v && P[l] < P[r]) merg(lret[v],rret[P[r]],P[l],ret[v]);
            else{
                vector<int> v1,v2;
                merg(lret[v],rret[P[l]],P[r],v1);
                merg(lret[P[l]],rret[v],P[r],v2);
                if(small(v1,v2)) ret[v] = v1;
                else ret[v] = v2;
            }
        }
    }

    return ret;
}
int main(){
    IO
    cin>>N; forf(i,1,N) cin>>P[i];
    auto ans = dfs(1,{});
    forf(i,1,sz(ans[P[1]])-1) cout<<ans[P[1]][i]<<" ";
}

Compilation message (stderr)

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