oj.uz

Submission #66313

# Submission time Handle Problem Language Result Execution time Memory
66313 2018-08-10T08:10:25 Z Just_Solve_The_Problem Sorting (IOI15_sorting) C++11
100 / 100
 730 ms 20216 KB 
#include <bits/stdc++.h>
//#include "sorting.h"
//#include "grader.cpp"

using namespace std;

const int nn = (int)1e6 + 7;

int x[nn], y[nn], p[nn], q[nn], n, s[nn], m;
int pos[nn], pos1[nn], p1[nn], p2[nn];

void upd(int a, int b) {
  swap(p1[a], p1[b]);
  p2[p1[a]] = a;
  p2[p1[b]] = b;
}

void upd1(int a, int b) {
  swap(pos[a], pos[b]);
  pos1[pos[a]] = a;
  pos1[pos[b]] = b;
}

bool check(int val) {
  iota(pos, pos + n, 0);
  iota(p1, p1 + n, 0);
  for (int i = 0; i < val; i++) {
    swap(pos[x[i]], pos[y[i]]);
  }
  for (int i = 0; i < n; i++) {
    p2[p1[i]] = i;
    pos1[pos[i]] = i;
  }
  int cur = 0, ppos;
  for (int i = val - 1; i >= 0; i--) {
    if (cur < n)
      ppos = pos1[cur];
    if (cur < n && s[cur] == p1[ppos]) {
      i++;
      cur++;
      continue;
    }
    if (cur < n && s[cur] != p1[ppos]) {
      upd(p2[s[cur]], ppos);
    }
    cur++;
    upd(x[i], y[i]);
    upd1(x[i], y[i]);
  }
  for (int i = 0; i < n; i++) {
    if (s[i] != p1[i]) return 0;
  }
  return 1;
}

int asd;

void make(int val) {
  iota(pos, pos + n, 0);
  iota(p1, p1 + n, 0);
  for (int i = 0; i < val; i++) {
    swap(pos[x[i]], pos[y[i]]);
  }
  for (int i = 0; i < n; i++) {
    p2[p1[i]] = i;
    pos1[pos[i]] = i;
  }
  bool fl = 0;
  int cur = 0, ppos;
  asd = val - 1;
  for (int i = val - 1; i >= 0; i--) {
    if (cur < n)
      ppos = pos1[cur];
    if (cur < n && s[cur] == p1[ppos]) {
      i++;
      cur++;
      continue;
    }
    if (cur < n && s[cur] != p1[ppos]) {
      p[asd] = p2[s[cur]];
      q[asd--] = ppos;
      upd(p2[s[cur]], ppos);
    }
    cur++;
    upd(x[i], y[i]);
    upd1(x[i], y[i]);
  }
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
  n = N; m = M;
  for (int i = 0; i < n; i++)
    s[i] = S[i];
  for (int i = 0; i < m; i++) {
    x[i] = X[i]; y[i] = Y[i];
  }
  int l = 0;
  int r = m;
  while (r - l > 1) {
    int mid = (l + r) >> 1;
    if (check(mid)) {
      r = mid;
    } else {
      l = mid;
    }
  }
  if (check(l)) r = l;
  make(r);
  for (int i = 0; i <= asd; i++) {
    P[i] = 0;
    Q[i] = 0;
  }
  for (int i = asd + 1; i < r; i++) {
    P[i] = p[i];
    Q[i] = q[i];
  }
  return r;
}

//main() {
//  int n;
//  cin >> n;
//  int S[n];
//  for (int i = 0; i < n; i++) {
//    cin >> S[i];
//  }
//  int m;
//  cin >> m;
//  int X[M], Y[M];
//  for (int i = 0; i < m; i++) {
//    cin >> X[i] >> Y[i];
//  }
//  int ans1[M], ans2[M];
//  int sz = findSwapPairs(n, S, m, X, Y, ans1, ans2);
//  cout << sz << endl;
//  for (int i = 0; i < sz; i++) {
//    cout << ans1[i] << ' ' << ans2[i] << endl;
//  }
//}

Compilation message

sorting.cpp: In function 'void make(int)':
sorting.cpp:68:8: warning: unused variable 'fl' [-Wunused-variable]
   bool fl = 0;
        ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 400 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 3 ms 384 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 2 ms 400 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 3 ms 512 KB Output is correct
16 Correct 3 ms 512 KB Output is correct
17 Correct 2 ms 512 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 3 ms 640 KB Output is correct
22 Correct 3 ms 640 KB Output is correct
23 Correct 4 ms 640 KB Output is correct
24 Correct 4 ms 640 KB Output is correct
25 Correct 4 ms 640 KB Output is correct
26 Correct 3 ms 640 KB Output is correct
27 Correct 3 ms 640 KB Output is correct

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Correct 4 ms 640 KB Output is correct
12 Correct 4 ms 512 KB Output is correct
13 Correct 3 ms 640 KB Output is correct
14 Correct 3 ms 512 KB Output is correct
15 Correct 152 ms 17912 KB Output is correct
16 Correct 307 ms 18320 KB Output is correct
17 Correct 636 ms 19192 KB Output is correct
18 Correct 141 ms 13432 KB Output is correct
19 Correct 453 ms 16852 KB Output is correct
20 Correct 515 ms 17400 KB Output is correct
21 Correct 488 ms 17528 KB Output is correct
22 Correct 202 ms 19608 KB Output is correct
23 Correct 276 ms 20088 KB Output is correct
24 Correct 694 ms 19780 KB Output is correct
25 Correct 730 ms 19448 KB Output is correct
26 Correct 486 ms 17356 KB Output is correct
27 Correct 390 ms 16632 KB Output is correct
28 Correct 503 ms 19320 KB Output is correct
29 Correct 405 ms 18680 KB Output is correct
30 Correct 284 ms 15756 KB Output is correct
31 Correct 422 ms 19064 KB Output is correct
32 Correct 168 ms 19400 KB Output is correct
33 Correct 570 ms 19576 KB Output is correct
34 Correct 380 ms 19704 KB Output is correct
35 Correct 318 ms 16632 KB Output is correct
36 Correct 61 ms 14328 KB Output is correct
37 Correct 547 ms 20216 KB Output is correct
38 Correct 619 ms 19344 KB Output is correct
39 Correct 559 ms 19448 KB Output is correct