Submission #34752964

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <bitset>
#include <complex>
#include <array>
#include <list>
#include <stack>
#include <valarray>

using namespace std;

typedef unsigned uint;
typedef long long Int;
typedef unsigned long long UInt;

const int INF = 1001001001;
const Int INFLL = 1001001001001001001LL;

template <typename T>
void pv(T a, T b)
{
  for (T i = a; i != b; ++i)
    cout << *i << " ";
  cout << endl;
}
template <typename T>
void chmin(T &a, T b)
{
  if (a > b)
    a = b;
}
template <typename T>
void chmax(T &a, T b)
{
  if (a < b)
    a = b;
}
int in()
{
  int x;
  scanf("%d", &x);
  return x;
}
double fin()
{
  double x;
  scanf("%lf", &x);
  return x;
}
Int lin()
{
  Int x;
  scanf("%lld", &x);
  return x;
}

int main()
{
  int N;
  cin >> N;
  vector<int> P(N), A(N, 0);
  Int am = 0;
  Int res = INFLL;
  for (int i = 0; i < N; ++i)
  {
    P[i] = in();
    A[(i - P[i] + N) % N]++;
    am += min((i - P[i] + N) % N, (P[i] - i + N) % N);
  }

  for (int i = 0; i < N; ++i)
  {
    A.push_back(A[i]);
  }
  for (int i = 0; i < N; ++i)
  {
    A.push_back(A[i]);
  }
  vector<int> S(A.size(), 0);
  for (int i = 0; i < (int)A.size(); ++i)
  {
    S[i] = A[i];
    if (i > 0)
      S[i] += S[i - 1];
  }

  int len = N / 2;
  int pos = 0, neg = (N + 1) / 2;
  for (int i = 0; i < N; ++i)
  {
    chmin(res, am);
    am += S[pos + len - 1] - (pos == 0 ? 0 : S[pos - 1]);
    am -= S[neg + len - 1] - (neg == 0 ? 0 : S[neg - 1]);
    pos = (pos - 1 + N) % N;
    neg = (neg - 1 + N) % N;
  }
  cout << res << endl;
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int in()’:
./Main.cpp:53:8: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   53 |   scanf("%d", &x);
      |   ~~~~~^~~~~~~~~~
./Main.cpp: In function ‘double fin()’:
./Main.cpp:59:8: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   59 |   scanf("%lf", &x);
      |   ~~~~~^~~~~~~~~~~
./Main.cpp: In function ‘Int lin()’:
./Main.cpp:65:8: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   65 |   scanf("%lld", &x);
      |   ~~~~~^~~~~~~~~~~~

Judge Result