oj.uz

Submission #1108252

# Submission time Handle Problem Language Result Execution time Memory
1108252 2024-11-03T14:04:12 Z lighton Swap (BOI16_swap) C++17
68 / 100
 1000 ms 10604 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;
    int tmp = now;
    while(tmp){
        if(1<=tmp && tmp<=N) p.pb(P[tmp]);
        if(1<=(tmp^1) && (tmp^1)<=N) p.pb(P[tmp^1]);
        tmp >>= 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), rret=dfs(r);
    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 336 KB Output is correct
7 Correct 2 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 468 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 2 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 468 KB Output is correct
11 Correct 3 ms 336 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 4 ms 336 KB Output is correct
14 Correct 3 ms 472 KB Output is correct
15 Correct 4 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 2 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 468 KB Output is correct
11 Correct 3 ms 336 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 4 ms 336 KB Output is correct
14 Correct 3 ms 472 KB Output is correct
15 Correct 4 ms 336 KB Output is correct
16 Correct 202 ms 4368 KB Output is correct
17 Correct 182 ms 4488 KB Output is correct
18 Correct 178 ms 4680 KB Output is correct
19 Correct 200 ms 4896 KB Output is correct
20 Correct 221 ms 4708 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 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 2 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 468 KB Output is correct
11 Correct 3 ms 336 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 4 ms 336 KB Output is correct
14 Correct 3 ms 472 KB Output is correct
15 Correct 4 ms 336 KB Output is correct
16 Correct 202 ms 4368 KB Output is correct
17 Correct 182 ms 4488 KB Output is correct
18 Correct 178 ms 4680 KB Output is correct
19 Correct 200 ms 4896 KB Output is correct
20 Correct 221 ms 4708 KB Output is correct
21 Correct 848 ms 10604 KB Output is correct
22 Correct 876 ms 9896 KB Output is correct
23 Correct 905 ms 10564 KB Output is correct
24 Execution timed out 1028 ms 10304 KB Time limit exceeded
25 Halted 0 ms 0 KB -