oj.uz

Submission #1108254

# Submission time Handle Problem Language Result Execution time Memory
1108254 2024-11-03T14:07:13 Z lighton Swap (BOI16_swap) C++17
100 / 100
 987 ms 11208 KB 
#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){
    if(1<=now && now<=N) p.pb(P[now]);
    if(1<=(now^1) && (now^1)<=N) p.pb(P[now^1]);
    unordered_map<int,vector<int> > ret;
    int l = now*2, r=now*2+1;
    unordered_map<int, vector<int> > lret,rret;
    if(r<=N) lret = dfs(l,p), rret=dfs(r,p);
    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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 3 ms 336 KB Output is correct
12 Correct 3 ms 336 KB Output is correct
13 Correct 3 ms 336 KB Output is correct
14 Correct 3 ms 336 KB Output is correct
15 Correct 3 ms 336 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 3 ms 336 KB Output is correct
12 Correct 3 ms 336 KB Output is correct
13 Correct 3 ms 336 KB Output is correct
14 Correct 3 ms 336 KB Output is correct
15 Correct 3 ms 336 KB Output is correct
16 Correct 168 ms 4220 KB Output is correct
17 Correct 193 ms 4232 KB Output is correct
18 Correct 173 ms 4440 KB Output is correct
19 Correct 208 ms 4500 KB Output is correct
20 Correct 205 ms 4520 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 3 ms 336 KB Output is correct
12 Correct 3 ms 336 KB Output is correct
13 Correct 3 ms 336 KB Output is correct
14 Correct 3 ms 336 KB Output is correct
15 Correct 3 ms 336 KB Output is correct
16 Correct 168 ms 4220 KB Output is correct
17 Correct 193 ms 4232 KB Output is correct
18 Correct 173 ms 4440 KB Output is correct
19 Correct 208 ms 4500 KB Output is correct
20 Correct 205 ms 4520 KB Output is correct
21 Correct 786 ms 9260 KB Output is correct
22 Correct 793 ms 8820 KB Output is correct
23 Correct 807 ms 8996 KB Output is correct
24 Correct 865 ms 9940 KB Output is correct
25 Correct 987 ms 11208 KB Output is correct