Submission #3848685


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 = 10;
    rep(i, divs) {
        int low = i * N / divs;
        int high = (i + 1) * N / divs - 1;
        while (high - low > 20) {
            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 1009 ms
Memory 3456 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 529 ms 3456 KB
11.txt 706 ms 3328 KB
12.txt 1003 ms 3328 KB
13.txt 1001 ms 3328 KB
14.txt 1003 ms 3328 KB
15.txt 1003 ms 3328 KB
16.txt 731 ms 3328 KB
17.txt 732 ms 3328 KB
18.txt 717 ms 3328 KB
19.txt 678 ms 3200 KB
2.txt 1003 ms 3328 KB
20.txt 722 ms 3328 KB
21.txt 740 ms 3328 KB
22.txt 732 ms 3328 KB
3.txt 527 ms 3328 KB
4.txt 706 ms 3328 KB
5.txt 706 ms 3328 KB
6.txt 1005 ms 3328 KB
7.txt 1009 ms 3328 KB
8.txt 897 ms 3072 KB
9.txt 1001 ms 3328 KB
sample1.txt 1 ms 256 KB
sample2.txt 1 ms 256 KB
sample3.txt 1 ms 256 KB