Submission #1113323

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1113323	2024-11-16T11:24:37 Z	duckindog	Line Town (CCO23_day1problem3)	C++17	6 / 25	55 ms	21632 KB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 500'000 + 10,
          MAX = 1'000'000'000'000'000;
int n;
int h[N];

int pref[N];

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

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

  int answer = MAX;  
  { // the number of 1 is odd
    deque<int> odd, even;
    for (int i = 1; i <= n; ++i) { 
      auto& vt = (i ^ (h[i] == 1)) & 1 ? odd : even;
      vt.push_back(i);
    }

    vector<int> sequence;
    for (int i = 1; i < n; ++i) { 
      auto& ret = pref[i];
      ret = pref[i - 1];

      auto& vt = i & 1 ? odd : even;
      if (!vt.size()) { ret = MAX; continue; }

      sequence.push_back(vt.front());
      ret += max(0ll, i - vt.front());
      vt.pop_front();
    }

    if (pref[n - 1] < MAX) { 
      answer = min(answer, pref[n - 1]);
      
      int total = 0;      
      { // i == n
        int i = n;

        auto& ret = pref[i];
        ret = pref[i - 1];

        auto& vt = (i ^ 1) & 1 ? odd : even;
        if (!vt.size()) ret = MAX;

        sequence.push_back(vt.front());
        ret += max(0ll, i - vt.front());
        total += max(0ll, i - vt.front());
        vt.pop_front();
      }
      
      for (int i = n - 2; i >= 1; i -= 2) { 
        swap(sequence[i - 1], sequence[i]);

        total += max(0ll, i - sequence[i - 1]);
        total += max(0ll, i + 1 - sequence[i]);
        
        answer = min(answer, pref[i - 1] + total);
      }
    }
  }
  
  { // the number of 1 is even
    deque<int> odd, even;
    for (int i = 1; i <= n; ++i) { 
      auto& vt = (i ^ (h[i] == 1)) & 1 ? odd : even;
      vt.push_back(i);
    }

    vector<int> sequence;
    for (int i = 1; i <= n; ++i) { 
      auto& ret = pref[i];
      ret = pref[i - 1];

      auto& vt = i & 1 ? odd : even;
      if (!vt.size()) { ret = MAX; continue; }

      sequence.push_back(vt.front());
      ret += max(0ll, i - vt.front());
      vt.pop_front();
    }
    
    if (pref[n] < MAX) { 
      answer = min(answer, pref[n]);
      
      int total = 0;
      for (int i = n - 1; i >= 1; i -= 2) { 
        swap(sequence[i - 1], sequence[i]);

        total += max(0ll, i - sequence[i - 1]);
        total += max(0ll, i + 1 - sequence[i]);

        answer = min(answer, pref[i - 1] + total);
      }
    }
  }

  cout << (answer == MAX ? -1 : answer) << "\n";
}

Subtask #1
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	336 KB	Output is correct
9	Correct	1 ms	336 KB	Output is correct
10	Correct	1 ms	336 KB	Output is correct
11	Correct	1 ms	336 KB	Output is correct
12	Correct	1 ms	336 KB	Output is correct
13	Correct	1 ms	336 KB	Output is correct

Subtask #2
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	336 KB	Output is correct
9	Correct	1 ms	336 KB	Output is correct
10	Correct	1 ms	336 KB	Output is correct
11	Correct	1 ms	336 KB	Output is correct
12	Correct	1 ms	336 KB	Output is correct
13	Correct	1 ms	336 KB	Output is correct
14	Correct	1 ms	336 KB	Output is correct
15	Correct	47 ms	21400 KB	Output is correct
16	Correct	52 ms	21620 KB	Output is correct
17	Correct	55 ms	21632 KB	Output is correct
18	Correct	45 ms	21604 KB	Output is correct
19	Correct	53 ms	21404 KB	Output is correct
20	Correct	41 ms	21624 KB	Output is correct
21	Correct	42 ms	21548 KB	Output is correct
22	Correct	41 ms	21624 KB	Output is correct
23	Correct	52 ms	21624 KB	Output is correct
24	Correct	41 ms	21632 KB	Output is correct

Subtask #3
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	336 KB	Output is correct
9	Correct	1 ms	336 KB	Output is correct
10	Correct	1 ms	336 KB	Output is correct
11	Correct	1 ms	336 KB	Output is correct
12	Correct	1 ms	336 KB	Output is correct
13	Correct	1 ms	336 KB	Output is correct
14	Incorrect	1 ms	504 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #4
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	336 KB	Output is correct
9	Correct	1 ms	336 KB	Output is correct
10	Correct	1 ms	336 KB	Output is correct
11	Correct	1 ms	336 KB	Output is correct
12	Correct	1 ms	336 KB	Output is correct
13	Correct	1 ms	336 KB	Output is correct
14	Correct	1 ms	336 KB	Output is correct
15	Correct	47 ms	21400 KB	Output is correct
16	Correct	52 ms	21620 KB	Output is correct
17	Correct	55 ms	21632 KB	Output is correct
18	Correct	45 ms	21604 KB	Output is correct
19	Correct	53 ms	21404 KB	Output is correct
20	Correct	41 ms	21624 KB	Output is correct
21	Correct	42 ms	21548 KB	Output is correct
22	Correct	41 ms	21624 KB	Output is correct
23	Correct	52 ms	21624 KB	Output is correct
24	Correct	41 ms	21632 KB	Output is correct
25	Incorrect	1 ms	504 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Subtask #5
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	336 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	336 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	336 KB	Output is correct
9	Correct	1 ms	336 KB	Output is correct
10	Correct	1 ms	336 KB	Output is correct
11	Correct	1 ms	336 KB	Output is correct
12	Correct	1 ms	336 KB	Output is correct
13	Correct	1 ms	336 KB	Output is correct
14	Incorrect	1 ms	504 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #8
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	336 KB	Output is correct
9	Correct	1 ms	336 KB	Output is correct
10	Correct	1 ms	336 KB	Output is correct
11	Correct	1 ms	336 KB	Output is correct
12	Correct	1 ms	336 KB	Output is correct
13	Correct	1 ms	336 KB	Output is correct
14	Correct	1 ms	336 KB	Output is correct
15	Correct	47 ms	21400 KB	Output is correct
16	Correct	52 ms	21620 KB	Output is correct
17	Correct	55 ms	21632 KB	Output is correct
18	Correct	45 ms	21604 KB	Output is correct
19	Correct	53 ms	21404 KB	Output is correct
20	Correct	41 ms	21624 KB	Output is correct
21	Correct	42 ms	21548 KB	Output is correct
22	Correct	41 ms	21624 KB	Output is correct
23	Correct	52 ms	21624 KB	Output is correct
24	Correct	41 ms	21632 KB	Output is correct
25	Incorrect	1 ms	504 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Submission #1113323

Compilation message