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 |
|
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 |