Submission #3848219


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 ret = LLONG_MAX;
    const int divs = 16;
    rep(i, divs) {
        int low = i * N / divs;
        int high = (i + 1) * N / divs - 1;
        while (high - low > 50) {
            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
Task E - Negative Doubling
User iwashi31
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2911 Byte
Status
Exec Time 2103 ms
Memory 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 1112 ms 3328 KB
11.txt 1538 ms 3328 KB
12.txt 2103 ms 3328 KB
13.txt 2103 ms 3328 KB
14.txt 2103 ms 3328 KB
15.txt 2103 ms 3328 KB
16.txt 1508 ms 3328 KB
17.txt 1510 ms 3328 KB
18.txt 1524 ms 3328 KB
19.txt 1385 ms 3200 KB
2.txt 2103 ms 3328 KB
20.txt 1523 ms 3328 KB
21.txt 1499 ms 3328 KB
22.txt 1505 ms 3328 KB
3.txt 1112 ms 3328 KB
4.txt 1539 ms 3328 KB
5.txt 1539 ms 3328 KB
6.txt 2103 ms 3328 KB
7.txt 2103 ms 3328 KB
8.txt 1824 ms 3072 KB
9.txt 2103 ms 3328 KB
sample1.txt 1 ms 256 KB
sample2.txt 1 ms 256 KB
sample3.txt 1 ms 256 KB