QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#118184#6627. Line Townhos_lyric#0 0ms4056kbC++143.2kb2023-07-03 10:20:312024-05-31 18:50:02

Judging History

你现在查看的是最新测评结果

  • [2024-05-31 18:50:02]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:4056kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-03 10:20:31]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


constexpr Int INF = 1001001001001001001LL;

int N;
vector<Int> A;

Int ans;

namespace sign {
void run() {
  vector<int> iss[3];
  for (int i = 0; i < N; ++i) {
    const int a = ((i&1)?-1:+1) * A[i];
    iss[(a < 0) ? 0 : (a == 0) ? 1 : 2].push_back(i);
  }
// cerr<<"iss = ";pv(iss,iss+3);
  int lens[3];
  for (int h = 0; h < 3; ++h) {
    lens[h] = iss[h].size();
  }
  
  vector<Int> head[3], tail[3];
  for (const int h : {0, 2}) {
    head[h].assign(lens[h] + 1, 0);
    tail[h].assign(lens[h] + 1, 0);
    for (int j = 0; j < lens[h]; ++j) {
      const int tar = (h == 0) ? (2 * j) : (2 * j + 1);
      head[h][j + 1] = (tar < N) ? (head[h][j] + abs(tar - iss[h][j])) : INF;
    }
    for (int j = lens[h]; --j >= 0; ) {
      const int tar = (h == 0) ? (2 * (N/2 - (lens[h]-j)) + 1) : (2 * (N-N/2 - (lens[h]-j)));
      tail[h][j] = (tar >= 0) ? (abs(tar - iss[h][j]) + tail[h][j + 1]) : INF;
    }
// cerr<<"-0+"[h]<<": "<<head[h]<<" "<<tail[h]<<endl;
  }
  
  vector<Int> zero(N - lens[1] + 1, 0);
  {
    Int now = 0;
    vector<int> cnt(N - lens[1] + 1, 0);
    for (int j = 0; j < lens[1]; ++j) {
      // |x+j - iss[1][j]|
      now += (iss[1][j] - j);
      ++cnt[iss[1][j] - j];
    }
    int slope = 0;
    for (int x = 0; x <= N - lens[1]; ++x) {
      zero[x] = now;
      slope += cnt[x];
      now += slope;
    }
  }
// cerr<<"zero = "<<zero<<endl;
  
  // 0's to [x, x + lens[1])
  for (int x = 0; x <= N - lens[1]; ++x) {
    if (x-x/2 <= lens[0] && x/2 <= lens[2]) {
      Int cost = 0;
      cost += head[0][x-x/2] + tail[0][x-x/2];
      cost += head[2][x/2] + tail[2][x/2];
      cost += zero[x];
// cerr<<x<<": "<<cost<<endl;
      chmin(ans, cost);
    }
  }
  ans /= 2;
}
}  // sign

int main() {
  for (; ~scanf("%d", &N); ) {
    A.resize(N);
    for (int i = 0; i < N; ++i) {
      scanf("%lld", &A[i]);
    }
    
    ans = INF;
    sign::run();
    printf("%lld\n", (ans >= INF / 2) ? -1 : ans);
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3828kb

input:

10
1 1 1 1 1 -1 -1 -1 1 -1

output:

8

result:

wrong answer 1st numbers differ - expected: '-1', found: '8'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Wrong Answer

Test #60:

score: 0
Wrong Answer
time: 0ms
memory: 4056kb

input:

10
3 10 5 -9 7 2 -6 1 8 0

output:

8

result:

wrong answer 1st numbers differ - expected: '-1', found: '8'

Subtask #6:

score: 0
Skipped

Dependency #5:

0%

Subtask #7:

score: 0
Skipped

Dependency #3:

0%

Subtask #8:

score: 0
Skipped

Dependency #1:

0%