oj.uz

Submission #1108262

# Submission time Handle Problem Language Result Execution time Memory
1108262 2024-11-03T14:16:26 Z lighton Swap (BOI16_swap) C++17
68 / 100
 1000 ms 10116 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);
#pragma GCC optimize("O3,Ofast,unroll-loops")
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: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.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 504 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 504 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 504 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 504 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 504 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 504 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 3 ms 336 KB Output is correct
12 Correct 2 ms 336 KB Output is correct
13 Correct 3 ms 336 KB Output is correct
14 Correct 3 ms 504 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 504 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 504 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 3 ms 336 KB Output is correct
12 Correct 2 ms 336 KB Output is correct
13 Correct 3 ms 336 KB Output is correct
14 Correct 3 ms 504 KB Output is correct
15 Correct 3 ms 336 KB Output is correct
16 Correct 167 ms 4176 KB Output is correct
17 Correct 196 ms 4168 KB Output is correct
18 Correct 162 ms 4424 KB Output is correct
19 Correct 193 ms 4460 KB Output is correct
20 Correct 185 ms 4460 KB Output is correct

Subtask #5
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 504 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 504 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 3 ms 336 KB Output is correct
12 Correct 2 ms 336 KB Output is correct
13 Correct 3 ms 336 KB Output is correct
14 Correct 3 ms 504 KB Output is correct
15 Correct 3 ms 336 KB Output is correct
16 Correct 167 ms 4176 KB Output is correct
17 Correct 196 ms 4168 KB Output is correct
18 Correct 162 ms 4424 KB Output is correct
19 Correct 193 ms 4460 KB Output is correct
20 Correct 185 ms 4460 KB Output is correct
21 Correct 762 ms 9452 KB Output is correct
22 Correct 852 ms 8764 KB Output is correct
23 Correct 803 ms 8992 KB Output is correct
24 Execution timed out 1000 ms 10116 KB Time limit exceeded
25 Halted 0 ms 0 KB -