Submission #1519804


Source Code Expand

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

VI aa, a, unzip(100010);
unordered_map<int, int> zip;
int n;
VI compress() {
  a = aa;
  sort(ALL(aa));
  aa.erase(unique(ALL(aa)), aa.end());
  REP(i, aa.size()) {
    zip[aa[i]] = i;
    unzip[i] = aa[i];
  }
  REP(i, a.size()) {
    a[i] = zip[a[i]];
  }
  return a;
}

int b[100010];
int c[100010];
signed main(void)
{
  cin >> n;
  REP(i, n) {
    int tmp;
    cin >> tmp;
    b[i] = tmp;
    aa.PB(tmp);
  }
  compress();
  sort(ALL(a));

  int ret = 0;
  REP(i, n) {
    // cout << b[i] << " " << zip[b[i]] << " " << c[zip[b[i]]] << endl;
    if(zip[b[i]]%2 != i%2) ret++;
  }
  cout << ret/2 << endl;

  return 0;
}

Submission Info

Submission Time
Task C - BBuBBBlesort!
User ferin_tech
Language C++14 (GCC 5.4.1)
Score 600
Code Size 1476 Byte
Status AC
Exec Time 78 ms
Memory 6288 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 2
AC × 24
Set Name Test Cases
Sample s1.txt, s2.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, s1.txt, s2.txt
Case Name Status Exec Time Memory
01.txt AC 78 ms 6288 KB
02.txt AC 76 ms 6288 KB
03.txt AC 76 ms 6288 KB
04.txt AC 76 ms 6288 KB
05.txt AC 56 ms 6288 KB
06.txt AC 56 ms 6288 KB
07.txt AC 56 ms 6288 KB
08.txt AC 44 ms 6288 KB
09.txt AC 44 ms 6288 KB
10.txt AC 43 ms 6288 KB
11.txt AC 44 ms 6288 KB
12.txt AC 44 ms 6288 KB
13.txt AC 44 ms 6288 KB
14.txt AC 56 ms 6288 KB
15.txt AC 56 ms 6288 KB
16.txt AC 56 ms 6288 KB
17.txt AC 56 ms 6288 KB
18.txt AC 1 ms 640 KB
19.txt AC 1 ms 640 KB
20.txt AC 1 ms 640 KB
21.txt AC 1 ms 640 KB
22.txt AC 1 ms 640 KB
s1.txt AC 1 ms 640 KB
s2.txt AC 1 ms 640 KB