oj.uz

Submission #588684

# Submission time Handle Problem Language Result Execution time Memory
588684 2022-07-03T20:39:11 Z MohammadAghil Swap (BOI16_swap) C++17
68 / 100
 770 ms 133192 KB 
      #include <bits/stdc++.h>
//   #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
    using namespace std;
  typedef long long ll;
   typedef pair<ll, ll> pp;
    #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
      #define per(i,r,l) for(int i = (r); i >= (l); i--)
        #define rep(i,l,r) for(int i = (l); i < (r); i++)
           #define all(x) begin(x), end(x)
              #define sz(x) (int)(x).size()
                  #define pb push_back
                      #define ss second
                           #define ff first
                                   void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
void IOS(){
     cin.tie(0) -> sync_with_stdio(0);
     // #ifndef ONLINE_JUDGE
     //      freopen("in.in", "r", stdin);
     //      freopen("out.out", "w", stdout);
     // #endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 998244353, maxn = 5e4 + 5, lg = 40, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}

int a[maxn], n;
vector<int> cand[maxn], dp[maxn][lg];

int get(int u, int x){
     return lower_bound(all(cand[u]), x) - begin(cand[u]);
}

void dfs(int r){
     int cnt = 0;
     if(r<<1 <= n) dfs(r<<1), cnt++;
     if(r<<1 < n) dfs(r<<1|1), cnt++;
     rep(i,0,sz(cand[r])){
          int x = cand[r][i];
          if(cnt == 0) dp[r][i].pb(a[x]);
          else if(cnt == 1){
               dp[r][i].pb(a[x]), dp[r][i].pb(a[r<<1]);
               if(a[x] > a[r<<1]) swap(dp[r][i][0], dp[r][i][1]); 
          }else{
               vector<int> mn(sz(dp[r<<1][0]) + sz(dp[r<<1|1][0]) + 1, n+1);
               rep(msk,0,4){
                    int lx = r<<1, rx = r<<1|1, p = x;
                    if(msk&1) swap(lx, p);
                    if(msk&2) swap(rx, p);
                    vector<int> cand{a[p]}, resl = dp[r<<1][get(r<<1, lx)], resr = dp[r<<1|1][get(r<<1|1, rx)];
                    int ptr1 = 0, ptr2 = 0, st = 0;
                    while(ptr1 < sz(resl) || ptr2 < sz(resr)){
                         int k = 1<<st;
                         while(k && ptr1 < sz(resl)) cand.pb(resl[ptr1++]), k--;
                         k = 1<<st;
                         while(k && ptr2 < sz(resr)) cand.pb(resr[ptr2++]), k--;
                         st++;
                    }
                    bool t = true;
                    rep(i,0,sz(mn)) if(mn[i] - cand[i]) {
                         t = mn[i] < cand[i];
                         break;
                    }
                    if(!t) mn = cand;
               }
               dp[r][i] = mn;
          }
     }
     if(cnt) rep(i,0,sz(cand[r<<1])) dp[r<<1][i].clear();
     if(cnt == 2) rep(i,0,sz(cand[r<<1])) dp[r<<1|1][i].clear();
}

int main(){ IOS();
     cin >> n;
     rep(i,1,n+1) cin >> a[i];
     rep(i,1,n+1){
          cand[i].pb(i);
          for(int j = i; j > 1; j >>= 1) cand[i].pb(j>>1), cand[i].pb(j^1);
          sort(all(cand[i]));
          while(sz(cand[i]) && cand[i].back() > n) cand[i].pop_back();
     }
     dfs(1);
     // rep(i,1,n+1){
     //      rep(j,0,sz(cand[i])){
     //           er(i, cand[i][j]);
     //           for(int c: dp[i][j]) cerr << c << ' '; cerr << '\n';
     //      }
     // }
     for(int c: dp[1][0]) cout << c << ' '; 
     return 0;  
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 48468 KB Output is correct
2 Correct 22 ms 48408 KB Output is correct
3 Correct 23 ms 48476 KB Output is correct
4 Correct 24 ms 48596 KB Output is correct
5 Correct 22 ms 48404 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 48468 KB Output is correct
2 Correct 22 ms 48408 KB Output is correct
3 Correct 23 ms 48476 KB Output is correct
4 Correct 24 ms 48596 KB Output is correct
5 Correct 22 ms 48404 KB Output is correct
6 Correct 21 ms 48384 KB Output is correct
7 Correct 22 ms 48468 KB Output is correct
8 Correct 22 ms 48400 KB Output is correct
9 Correct 22 ms 48376 KB Output is correct
10 Correct 22 ms 48420 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 48468 KB Output is correct
2 Correct 22 ms 48408 KB Output is correct
3 Correct 23 ms 48476 KB Output is correct
4 Correct 24 ms 48596 KB Output is correct
5 Correct 22 ms 48404 KB Output is correct
6 Correct 21 ms 48384 KB Output is correct
7 Correct 22 ms 48468 KB Output is correct
8 Correct 22 ms 48400 KB Output is correct
9 Correct 22 ms 48376 KB Output is correct
10 Correct 22 ms 48420 KB Output is correct
11 Correct 36 ms 49228 KB Output is correct
12 Correct 33 ms 49316 KB Output is correct
13 Correct 31 ms 49236 KB Output is correct
14 Correct 30 ms 49332 KB Output is correct
15 Correct 31 ms 49364 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 48468 KB Output is correct
2 Correct 22 ms 48408 KB Output is correct
3 Correct 23 ms 48476 KB Output is correct
4 Correct 24 ms 48596 KB Output is correct
5 Correct 22 ms 48404 KB Output is correct
6 Correct 21 ms 48384 KB Output is correct
7 Correct 22 ms 48468 KB Output is correct
8 Correct 22 ms 48400 KB Output is correct
9 Correct 22 ms 48376 KB Output is correct
10 Correct 22 ms 48420 KB Output is correct
11 Correct 36 ms 49228 KB Output is correct
12 Correct 33 ms 49316 KB Output is correct
13 Correct 31 ms 49236 KB Output is correct
14 Correct 30 ms 49332 KB Output is correct
15 Correct 31 ms 49364 KB Output is correct
16 Correct 761 ms 132692 KB Output is correct
17 Correct 770 ms 133192 KB Output is correct
18 Correct 755 ms 133040 KB Output is correct
19 Correct 753 ms 133176 KB Output is correct
20 Correct 747 ms 132948 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 48468 KB Output is correct
2 Correct 22 ms 48408 KB Output is correct
3 Correct 23 ms 48476 KB Output is correct
4 Correct 24 ms 48596 KB Output is correct
5 Correct 22 ms 48404 KB Output is correct
6 Correct 21 ms 48384 KB Output is correct
7 Correct 22 ms 48468 KB Output is correct
8 Correct 22 ms 48400 KB Output is correct
9 Correct 22 ms 48376 KB Output is correct
10 Correct 22 ms 48420 KB Output is correct
11 Correct 36 ms 49228 KB Output is correct
12 Correct 33 ms 49316 KB Output is correct
13 Correct 31 ms 49236 KB Output is correct
14 Correct 30 ms 49332 KB Output is correct
15 Correct 31 ms 49364 KB Output is correct
16 Correct 761 ms 132692 KB Output is correct
17 Correct 770 ms 133192 KB Output is correct
18 Correct 755 ms 133040 KB Output is correct
19 Correct 753 ms 133176 KB Output is correct
20 Correct 747 ms 132948 KB Output is correct
21 Runtime error 61 ms 98896 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -