oj.uz

Submission #1108260

# Submission time Handle Problem Language Result Execution time Memory
1108260 2024-11-03T14:15:48 Z lighton Swap (BOI16_swap) C++17
100 / 100
 979 ms 10060 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))];
    }
}
void dfs(int now, vector<int> p, unordered_map<int, vector<int> > &ret){
    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;
    unordered_map<int, vector<int> > lret,rret;
    if(r<=N) dfs(l,p,lret), dfs(r,p,rret);
    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;
            }
        }
    }
}
int main(){
    IO
    cin>>N; forf(i,1,N) cin>>P[i];
    unordered_map<int, vector<int> > ans;
    dfs(1,{},ans);
    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 336 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 336 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 2 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 4 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 336 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 2 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 4 ms 336 KB Output is correct
15 Correct 3 ms 336 KB Output is correct
16 Correct 177 ms 4168 KB Output is correct
17 Correct 148 ms 4244 KB Output is correct
18 Correct 187 ms 4424 KB Output is correct
19 Correct 207 ms 4380 KB Output is correct
20 Correct 205 ms 4424 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 336 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 2 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 4 ms 336 KB Output is correct
15 Correct 3 ms 336 KB Output is correct
16 Correct 177 ms 4168 KB Output is correct
17 Correct 148 ms 4244 KB Output is correct
18 Correct 187 ms 4424 KB Output is correct
19 Correct 207 ms 4380 KB Output is correct
20 Correct 205 ms 4424 KB Output is correct
21 Correct 743 ms 9148 KB Output is correct
22 Correct 758 ms 8884 KB Output is correct
23 Correct 769 ms 8812 KB Output is correct
24 Correct 936 ms 10060 KB Output is correct
25 Correct 979 ms 9924 KB Output is correct