| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 414265 |
2021-05-30T09:41:31 Z |
Blagojce |
Swap (BOI16_swap) |
C++11 |
|
16 ms |
22236 KB |
#include <bits/stdc++.h>
#include <cstdio>
#pragma GCC optimize("O3")
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const ll inf = 1e18;
const ll mod = 1000000007;
const ld eps = 1e-13;
const ld pi = 3.14159265359;
mt19937 _rand(time(NULL));
clock_t timer = clock();
const int mxn = 400000;
int n;
int a[mxn];
unordered_map<int, vector<int> > f[mxn];
//vector<int> f[mxn][mxn];
void combine(int a, int x, int b, int y, vector<int> &r){
int p = 0;
int l = 1;
vector<int> ret;
while(p < (int)f[a][x].size()){
fr(k, 0, l){
ret.pb(f[a][x][p+k]);
}
fr(k, 0, l){
ret.pb(f[b][y][p+k]);
}
p += l;
l *= 2;
}
}
vector<int> lex(vector<int> v1, vector<int> v2){
fr(i, 0, (int)v1.size()){
if(v1[i] < v2[i]) return v1;
else if(v1[i] > v2[i]) return v2;
}
return v1;
}
void solve(){
cin >> n;
fr(i, 1, n+1){
cin >> a[i];
}
int orgn = n;
int m = n;
while(m+1 - ((m+1)&-(m+1)) != 0){
++m;
}
fr(i, n+1, m+1){
a[i] = i;
}
n = m;
for(int i = n; i >= 1; i --){
vector<int> cand;
for(int j = i; j >= 1; j /= 2){
cand.pb(a[j]);
if(j != 1){
if(j % 2){
cand.pb(a[j-1]);
}
else{
cand.pb(a[j+1]);
}
}
}
for(auto j : cand){
if(i*2 > n){
f[i][j] = {j};
}
else{
int mi = min(j, min(a[i*2], a[i*2+1]));
if(j == mi){
combine(i*2, a[i*2], i*2+1, a[i*2+1], f[i][j]);
}
else if(a[i*2] == mi){
combine(i*2, j, i*2+1, a[i*2+1], f[i][j]);
}
else{
vector<int> g1;
combine(i*2, a[i*2], i*2+1, j, g1);
vector<int> g2;
combine(i*2, j, i*2+1, a[i*2], g2);
f[i][j] = min(g1, g2);
}
f[i][j].insert(f[i][j].begin(), mi);
}
}
}
fr(i, 0, orgn){
cout<<f[1][a[1]][i]<<' ';
}
}
int main(){
//freopen("t.in.25", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
//
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
22236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
22236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
22236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
22236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
22236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
