Submission #1551949


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) GET_MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cout<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cout<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 1120000000

int main(){
  int n;
  cin>>n;
  vector<int> vec(n);
  rep(i,n) cin>>vec[i];

  rep(i,2*n){
    auto exec = [&](){
      vector<int> v( (n+i)*2 );
      rep(j,n) v[i+j] = vec[j];
      rep(j,n+i) v[i+n+j] = 1000000001;
      set<int> s;
      rep(j,n) s.insert(vec[j]);
      for(int j=i-1; j>=0; j--){
        v[j] = -1;
        for(int k=min(v[2*j+1], v[2*j+2])-1; k>=0; k--){
          if(s.count(k)==0){
            v[j] = k;
            s.insert(k);
            break;
          }
        }
        if(v[j]==-1) return false;
      }

      // check
      rep(j,i+n){
        if(2*j+1 >= i+n) break;
        if(v[j]>=v[2*j+1] || v[j]>=v[2*j+2]) return false;
      }

      cout << i+n << endl;
      return true;
    };
    if(exec()) return 0;
  }

  cout << -1 << endl;

  return 0;
}

Submission Info

Submission Time
Task D - 壊れかけのヒープ
User tossy
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1778 Byte
Status AC
Exec Time 5 ms
Memory 256 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 33
Set Name Test Cases
All hard-01, hard-02, hard-03, hard-04, hard-05, hard-06, hard-07, hard-08, hard-09, hard-10, hard-11, hard-12, hard-corner-01, hard-corner-02, hard-corner-03, hard-corner-04, hard-corner-05, hard-random-01, hard-random-02, hard-random-03, hard-random-04, hard-random-05, hard-random-06, hard-semirandom-01, hard-semirandom-02, hard-semirandom-03, hard-semirandom-04, hard-semirandom-05, hard-semirandom-06, sample-01, sample-02, sample-03, sample-04
Case Name Status Exec Time Memory
hard-01 AC 1 ms 256 KB
hard-02 AC 1 ms 256 KB
hard-03 AC 1 ms 256 KB
hard-04 AC 2 ms 256 KB
hard-05 AC 1 ms 256 KB
hard-06 AC 1 ms 256 KB
hard-07 AC 1 ms 256 KB
hard-08 AC 1 ms 256 KB
hard-09 AC 2 ms 256 KB
hard-10 AC 1 ms 256 KB
hard-11 AC 2 ms 256 KB
hard-12 AC 1 ms 256 KB
hard-corner-01 AC 1 ms 256 KB
hard-corner-02 AC 1 ms 256 KB
hard-corner-03 AC 1 ms 256 KB
hard-corner-04 AC 2 ms 256 KB
hard-corner-05 AC 5 ms 256 KB
hard-random-01 AC 1 ms 256 KB
hard-random-02 AC 1 ms 256 KB
hard-random-03 AC 1 ms 256 KB
hard-random-04 AC 4 ms 256 KB
hard-random-05 AC 3 ms 256 KB
hard-random-06 AC 2 ms 256 KB
hard-semirandom-01 AC 1 ms 256 KB
hard-semirandom-02 AC 1 ms 256 KB
hard-semirandom-03 AC 1 ms 256 KB
hard-semirandom-04 AC 4 ms 256 KB
hard-semirandom-05 AC 3 ms 256 KB
hard-semirandom-06 AC 2 ms 256 KB
sample-01 AC 1 ms 256 KB
sample-02 AC 1 ms 256 KB
sample-03 AC 1 ms 256 KB
sample-04 AC 1 ms 256 KB