oj.uz

Submission #588678

# Submission time Handle Problem Language Result Execution time Memory
588678 2022-07-03T20:32:53 Z MohammadAghil Swap (BOI16_swap) C++17
48 / 100
 864 ms 176580 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 = 2e5 + 5, lg = 20, 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;
          }
     }
}

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 44 ms 98940 KB Output is correct
2 Correct 45 ms 98848 KB Output is correct
3 Correct 44 ms 98872 KB Output is correct
4 Correct 50 ms 98952 KB Output is correct
5 Correct 50 ms 99052 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 98940 KB Output is correct
2 Correct 45 ms 98848 KB Output is correct
3 Correct 44 ms 98872 KB Output is correct
4 Correct 50 ms 98952 KB Output is correct
5 Correct 50 ms 99052 KB Output is correct
6 Correct 43 ms 98956 KB Output is correct
7 Correct 44 ms 98840 KB Output is correct
8 Correct 45 ms 99024 KB Output is correct
9 Correct 44 ms 98952 KB Output is correct
10 Correct 45 ms 98960 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 98940 KB Output is correct
2 Correct 45 ms 98848 KB Output is correct
3 Correct 44 ms 98872 KB Output is correct
4 Correct 50 ms 98952 KB Output is correct
5 Correct 50 ms 99052 KB Output is correct
6 Correct 43 ms 98956 KB Output is correct
7 Correct 44 ms 98840 KB Output is correct
8 Correct 45 ms 99024 KB Output is correct
9 Correct 44 ms 98952 KB Output is correct
10 Correct 45 ms 98960 KB Output is correct
11 Correct 52 ms 99812 KB Output is correct
12 Correct 52 ms 99832 KB Output is correct
13 Correct 56 ms 99824 KB Output is correct
14 Correct 52 ms 99836 KB Output is correct
15 Correct 53 ms 99816 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 98940 KB Output is correct
2 Correct 45 ms 98848 KB Output is correct
3 Correct 44 ms 98872 KB Output is correct
4 Correct 50 ms 98952 KB Output is correct
5 Correct 50 ms 99052 KB Output is correct
6 Correct 43 ms 98956 KB Output is correct
7 Correct 44 ms 98840 KB Output is correct
8 Correct 45 ms 99024 KB Output is correct
9 Correct 44 ms 98952 KB Output is correct
10 Correct 45 ms 98960 KB Output is correct
11 Correct 52 ms 99812 KB Output is correct
12 Correct 52 ms 99832 KB Output is correct
13 Correct 56 ms 99824 KB Output is correct
14 Correct 52 ms 99836 KB Output is correct
15 Correct 53 ms 99816 KB Output is correct
16 Incorrect 864 ms 176580 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 98940 KB Output is correct
2 Correct 45 ms 98848 KB Output is correct
3 Correct 44 ms 98872 KB Output is correct
4 Correct 50 ms 98952 KB Output is correct
5 Correct 50 ms 99052 KB Output is correct
6 Correct 43 ms 98956 KB Output is correct
7 Correct 44 ms 98840 KB Output is correct
8 Correct 45 ms 99024 KB Output is correct
9 Correct 44 ms 98952 KB Output is correct
10 Correct 45 ms 98960 KB Output is correct
11 Correct 52 ms 99812 KB Output is correct
12 Correct 52 ms 99832 KB Output is correct
13 Correct 56 ms 99824 KB Output is correct
14 Correct 52 ms 99836 KB Output is correct
15 Correct 53 ms 99816 KB Output is correct
16 Incorrect 864 ms 176580 KB Output isn't correct
17 Halted 0 ms 0 KB -