oj.uz

Submission #1108257

# Submission time Handle Problem Language Result Execution time Memory
1108257 2024-11-03T14:13:01 Z lighton Swap (BOI16_swap) C++17
68 / 100
 482 ms 262144 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[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

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 4 ms 11344 KB Output is correct
2 Correct 6 ms 11428 KB Output is correct
3 Correct 4 ms 11344 KB Output is correct
4 Correct 4 ms 11344 KB Output is correct
5 Correct 3 ms 11344 KB Output is correct

Subtask #2
11.0 / 11.0

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

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11344 KB Output is correct
2 Correct 6 ms 11428 KB Output is correct
3 Correct 4 ms 11344 KB Output is correct
4 Correct 4 ms 11344 KB Output is correct
5 Correct 3 ms 11344 KB Output is correct
6 Correct 4 ms 11344 KB Output is correct
7 Correct 4 ms 11344 KB Output is correct
8 Correct 3 ms 11344 KB Output is correct
9 Correct 4 ms 11516 KB Output is correct
10 Correct 3 ms 11344 KB Output is correct
11 Correct 7 ms 13136 KB Output is correct
12 Correct 7 ms 13308 KB Output is correct
13 Correct 7 ms 13304 KB Output is correct
14 Correct 11 ms 13136 KB Output is correct
15 Correct 7 ms 13136 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11344 KB Output is correct
2 Correct 6 ms 11428 KB Output is correct
3 Correct 4 ms 11344 KB Output is correct
4 Correct 4 ms 11344 KB Output is correct
5 Correct 3 ms 11344 KB Output is correct
6 Correct 4 ms 11344 KB Output is correct
7 Correct 4 ms 11344 KB Output is correct
8 Correct 3 ms 11344 KB Output is correct
9 Correct 4 ms 11516 KB Output is correct
10 Correct 3 ms 11344 KB Output is correct
11 Correct 7 ms 13136 KB Output is correct
12 Correct 7 ms 13308 KB Output is correct
13 Correct 7 ms 13304 KB Output is correct
14 Correct 11 ms 13136 KB Output is correct
15 Correct 7 ms 13136 KB Output is correct
16 Correct 432 ms 170832 KB Output is correct
17 Correct 439 ms 170568 KB Output is correct
18 Correct 482 ms 170696 KB Output is correct
19 Correct 454 ms 170892 KB Output is correct
20 Correct 435 ms 170940 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11344 KB Output is correct
2 Correct 6 ms 11428 KB Output is correct
3 Correct 4 ms 11344 KB Output is correct
4 Correct 4 ms 11344 KB Output is correct
5 Correct 3 ms 11344 KB Output is correct
6 Correct 4 ms 11344 KB Output is correct
7 Correct 4 ms 11344 KB Output is correct
8 Correct 3 ms 11344 KB Output is correct
9 Correct 4 ms 11516 KB Output is correct
10 Correct 3 ms 11344 KB Output is correct
11 Correct 7 ms 13136 KB Output is correct
12 Correct 7 ms 13308 KB Output is correct
13 Correct 7 ms 13304 KB Output is correct
14 Correct 11 ms 13136 KB Output is correct
15 Correct 7 ms 13136 KB Output is correct
16 Correct 432 ms 170832 KB Output is correct
17 Correct 439 ms 170568 KB Output is correct
18 Correct 482 ms 170696 KB Output is correct
19 Correct 454 ms 170892 KB Output is correct
20 Correct 435 ms 170940 KB Output is correct
21 Runtime error 400 ms 262144 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -