| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1108255 |
2024-11-03T14:11:11 Z |
lighton |
Swap (BOI16_swap) |
C++17 |
|
3 ms |
11344 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;
unordered_map<int, vector<int> > lret,rret;
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(lret[P[l]],rret[P[r]],v,dp[now][v]);
else if(P[l] < v && P[l] < P[r]) merg(lret[v],rret[P[r]],P[l],dp[now][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)) dp[now][v] = v1;
else dp[now][v] = v2;
}
}
}
}
int main(){
IO
cin>>N; forf(i,1,N) cin>>P[i];
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;
| ~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
11344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
11344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
11344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
11344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
11344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
