Contest Duration: ~ (local time) (120 minutes)

Submission #3847909

Source Code Expand

Copy
```#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

#define int long long
#define MOD7 1000000007
#define MOD9 1000000009

#define rep(i, n) for (int i = 0; i < (n); i++)
#define itrep(i, a) for (auto i = (a).begin(); i != (a).end(); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()
#define mp(a, b) make_pair((a), (b))

using namespace std;

int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, -1, 0, 1 };

template<class T> void inputVector(vector<T>& v, int n) {
v.resize(n);
for (int i = 0; i < v.size(); i++) cin >> v[i];
}

int N;
vector<int> A;
vector<double> B;

int check(int firstPlus) {
int cnt = 0;
if (firstPlus > 0) {
cnt++;
double now = B[firstPlus - 1] + 1;
for (int i = firstPlus - 2; i >= 0; i--) {
int diff = max(0LL, (int) ceil(now - B[i]));
if (diff % 2 == 0) diff++;
now = B[i] + diff;
cnt += diff;
}
}
double now = B[firstPlus];
for (int i = firstPlus + 1; i < N; i++) {
int diff = max(0LL, (int) ceil(now - B[i]));
if (diff % 2) diff++;
now = B[i] + diff;
cnt += diff;
}
return cnt;
}

signed main() {
cin >> N;

A.resize(N);
rep(i, N) scanf("%lld", &A[i]);

B.resize(N);

rep(i, N) {
B[i] = log2(A[i]);
//cerr << B[i] << " ";
}
//cerr << endl;

//REP(i, 1, N - 1) {
//    memo1[i] = 1;
//    if (i > 1) {
//        if (B[i - 2] < B[i - 1]) {
//            int diff = ceil(B[i - 1] - B[i - 2]);
//            if (diff % 2) diff++;
//            memo1[i] += (i - 1) * diff;
//        }
//    }
//    cerr << "memo1[" << i << "] = " << memo1[i] << endl;
//}

int low = 0;
int high = N / 2;
while (high - low > 100) {
int mid1 = low + (high - low) / 3;
int mid2 = low + (high - low) * 2 / 3;
int val1 = check(mid1);
int val2 = check(mid2);
//cerr << "low:" << low << " high:" << high << endl;
if (val1 < val2) {
high = mid2;
} else {
low = mid1;
}
}

int ret = LLONG_MAX;
REP(i, low, high) {
int cnt = check(i);

ret = min(ret, cnt);
//cerr << "firstPlus:" << i << " cnt:" << cnt << endl;
}

low = N / 2 + 1;
high = N - 1;
while (high - low > 100) {
int mid1 = low + (high - low) / 3;
int mid2 = low + (high - low) * 2 / 3;
int val1 = check(mid1);
int val2 = check(mid2);
//cerr << "low:" << low << " high:" << high << endl;
if (val1 < val2) {
high = mid2;
} else {
low = mid1;
}
}

REP(i, low, high) {
int cnt = check(i);

ret = min(ret, cnt);
//cerr << "firstPlus:" << i << " cnt:" << cnt << endl;
}

cout << ret << endl;

return 0;
}
```

#### Submission Info

Submission Time 2018-12-22 22:28:39+0900 E - Negative Doubling iwashi31 C++14 (GCC 5.4.1) 0 3324 Byte WA 445 ms 3328 KB

#### Compile Error

```./Main.cpp: In function ‘int main()’:
./Main.cpp:69:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
rep(i, N) scanf("%lld", &A[i]);
^
```

#### Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample1.txt, sample2.txt, sample3.txt
All 0 / 800 sample1.txt, sample2.txt, sample3.txt, 1.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 2.txt, 20.txt, 21.txt, 22.txt, 3.txt, 4.txt, 5.txt, 6.txt, 7.txt, 8.txt, 9.txt, sample1.txt, sample2.txt, sample3.txt
Case Name Status Exec Time Memory
1.txt 1 ms 256 KB
10.txt 198 ms 3328 KB
11.txt 302 ms 3328 KB
12.txt 412 ms 3328 KB
13.txt 412 ms 3328 KB
14.txt 413 ms 3328 KB
15.txt 412 ms 3328 KB
16.txt 298 ms 3328 KB
17.txt 297 ms 3328 KB
18.txt 301 ms 3328 KB
19.txt 349 ms 3200 KB
2.txt 412 ms 3328 KB
20.txt 301 ms 3328 KB
21.txt 298 ms 3328 KB
22.txt 298 ms 3328 KB
3.txt 198 ms 3328 KB
4.txt 301 ms 3328 KB
5.txt 301 ms 3328 KB
6.txt 412 ms 3328 KB
7.txt 412 ms 3328 KB
8.txt 445 ms 3072 KB
9.txt 412 ms 3328 KB
sample1.txt 1 ms 256 KB
sample2.txt 1 ms 256 KB
sample3.txt 1 ms 256 KB