Submission #1124620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124620		lmToT27	Line Town (CCO23_day1problem3)	C++20	6 / 25	46 ms	20216 KiB

Main

#include <bits/stdc++.h>
#define all(dataStructure) dataStructure.begin(),dataStructure.end()

using namespace std;

typedef long long ll;

const int MAX = 5e5 + 3;
const ll inf = 1e17;
const ll MOD[] = {1000000007, 998244353};

int n, h[MAX];
ll prefix[MAX], suffix[MAX];
int pPos[MAX][2], sPos[MAX][2];

void Solve() {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> h[i];

        vector <int> t[2];
        for (int i = 1; i <= n; i++) {
                if (i & 1) {
                        if (h[i] == 1) t[0].push_back(i);
                        else t[1].push_back(i);
                } else {
                        if (h[i] == -1) t[0].push_back(i);
                        else t[1].push_back(i);
                }
        }

        pPos[0][0] = 0;
        pPos[0][1] = 0;

        for (int i = 1; i <= n; i++) {
                prefix[i] = prefix[i - 1];
                pPos[i][0] = pPos[i - 1][0];
                pPos[i][1] = pPos[i - 1][1];

                int id = i & 1;
                if (pPos[i][id] != (int)t[id].size()) {
                        prefix[i] += max(0ll, 1ll * t[id][pPos[i][id]++] - i);
                } else {
                        prefix[i] = inf;
                }
        }

        sPos[n + 1][0] = (int)t[0].size() - 1;
        sPos[n + 1][1] = (int)t[1].size() - 1;

        for (int i = n; i >= 1; i--) {
                suffix[i] = suffix[i + 1];
                sPos[i][0] = sPos[i + 1][0];
                sPos[i][1] = sPos[i + 1][1];

                int id = i & 1 ^ 1;
                if (sPos[i][id] >= 0) {
                        suffix[i] += max(0ll, 1ll * t[id][sPos[i][id]--] - i);
                } else {
                        suffix[i] = inf;
                }
        }

        ll ans = inf;

        for (int i = 0; i <= n; i++) {
                if (sPos[i + 1][0] == pPos[i][0] - 1) ans = min(ans, prefix[i] + suffix[i + 1]);
        }

        cout << (ans == inf ? -1 : ans);
}

int32_t main() {
        std::ios_base::sync_with_stdio(0);
        std::cin.tie(0); std::cout.tie(0);

        #define TASK ""
        if (fopen(TASK".INP", "r")) {
                freopen(TASK".INP", "r", stdin);
                freopen(TASK".OUT", "w", stdout);
        }

        if (fopen("TASK.INP", "r")) {
                freopen("TASK.INP", "r", stdin);
                freopen("TASK.OUT", "w", stdout);
        }

        /* int TEST = 1; cin >> TEST; while (TEST--) */ Solve();

        cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
        return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:78:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |                 freopen(TASK".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:79:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |                 freopen(TASK".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:83:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |                 freopen("TASK.INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:84:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |                 freopen("TASK.OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 0 / 3
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 3
• Subtask 7: 0 / 2
• Subtask 8: 0 / 3