Submission #713661

#	Time	Username	Problem	Language	Result	Execution time	Memory
713661		mtxas	Potatoes and fertilizers (LMIO19_bulves)	C++14	24 / 100	110 ms	13224 KiB

bulves

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define int long long
#define DISABLE_PRINTF
#ifdef DISABLE_PRINTF
#define printf(...)
#endif // DISABLE_PRINTF
using namespace std;
void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1);
    for(int i = 1; i <= n; ++i)
    {
        cin >> a[i] >> b[i];
    }
    int A = 0;
    int B = 0;
    for(int i = 1; i <= n; ++i)
    {
        A += a[i], B += b[i];
    }
    if(A == B)
    {
        /// solve it
        int ans = 0;
        int aid = 1, bid = 1;
        for(; bid <= n; ++bid)
        {
            for(; b[bid] > 0; ++aid)
            {
                int take = min(a[aid], b[bid]);
                b[bid] -= take;
                a[aid] -= take;
                ans += take * abs(bid - aid);
                if(b[bid] == 0)
                {
                    break;
                }
            }
        }
        cout << ans;
    }
    else if(A == B + 1)
    {
        vector<int> pref(n + 1), suff(n + 2);
        vector<int> prefLast(n + 1), suffLast(n + 2);
        vector<int> bcopy = b;
        vector<int> acopy = a;
        /// calc the pref
        int aid = 1;
        for(int i = 1; i <= n; ++i)
        {
            pref[i] = pref[i - 1];
            for(; b[i] > 0; aid += (a[aid] == 0))
            {
                int take = min(a[aid], b[i]);
                b[i] -= take;
                a[aid] -= take;
                pref[i] += abs(i - aid) * take;
                if(take == 0) continue;
                prefLast[i] = aid;
            }
        }
        a = acopy;
        b = bcopy;
        /// calc the suff
        aid = n;
        for(int i = n; i >= 1; --i)
        {
            suff[i] = suff[i + 1];
            for(; b[i] > 0; aid -= (a[aid] == 0))
            {
                int take = min(a[aid], b[i]);
                b[i] -= take;
                a[aid] -= take;
                suff[i] += abs(aid - i) * take;
                if(take == 0) continue;
                suffLast[i] = aid;
            }
        }
        a = acopy;
        b = bcopy;
        /// calc ferPref and ferSuff
        vector<int> ferPref(n + 1), ferSuff(n + 2);
        vector<int> potPref(n + 1), potSuff(n + 2);
        for(int i = 1; i <= n; ++i)
        {
            ferPref[i] = ferPref[i - 1] + a[i];
            ferSuff[n + 1 - i] = ferSuff[n + 1 - i + 1] + a[n + 1 - i];
            potPref[i] = potPref[i - 1] + b[i];
            potSuff[n + 1 - i] = potSuff[n + 1 - i + 1] + b[n + 1 - i];
        }
        /// calc the answer
        int ans = min(pref[n], suff[1]);
        vector<int> potIds;
        for(int i = 1; i <= n; ++i)
        {
            if(b[i] > 0)
            {
                potIds.push_back(i);
            }
        }
        printf("|potIds| = %d\n", (int) potIds.size());
        for(int j = 0; j < potIds.size() - 1; ++j)
        {
            int l = potIds[j];
            int r = potIds[j + 1];
            int initAns = pref[l] + suff[r];
            int curAns = initAns;
            /// find the location of fertilizer
            int fl = prefLast[l];
            int fr = suffLast[r];
            int flSum = ferPref[fl];
            int frSum = ferSuff[fr];
            int blSum = potPref[l];
            int brSum = potSuff[r];
            printf("(l, r) = (%d, %d)\n(fl, fr) = (%d, %d)\n(flSum, frSum) = (%d, %d)\n(blSum, brSum) = (%d, %d)\n", l, r, fl, fr, flSum, frSum, blSum, brSum);
            if(fl == fr) continue;
            assert(blSum + brSum == potPref[n]);
            assert(flSum + frSum == ferPref[n] - 1 || flSum + frSum == ferPref[n]);
            if(flSum == blSum && frSum == brSum)
            {
                for(int q = fl + 1; q < fr; ++q)
                {
                    if(a[q] > 0)
                    {
                        curAns = min({curAns,
                                      initAns + abs(l - q) - abs(l - fl),
                                      initAns + abs(r - q) - abs(r - fr)});
                        break;
                    }
                    assert(q != fr - 1);
                }
            }
            else if(flSum == blSum - 1)
            {
                curAns = min(curAns, initAns + abs(r - fl) - abs(r - fr));
            }
            else if(frSum == brSum - 1)
            {
                curAns = min(curAns, initAns + abs(l - fr) - abs(l - fl));
            }
            else
            {
                assert(false);
            }
            ans = min(ans, curAns);
        }
        cout << ans << '\n';
    }
}
signed main()
{
#ifdef EVAL
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
#endif // EVAL
    solve();
}

Compilation message (stderr)

bulves.cpp: In function 'void solve()':
bulves.cpp:106:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for(int j = 0; j < potIds.size() - 1; ++j)
      |                        ~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 24 / 24
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 36