Submission #861301

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
861301	2023-10-15 23:18:07	pedroslrey	Sorting (IOI15_sorting)	C++14	100 / 100	220 ms	20276 KiB

sorting

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
#include "sorting.h"
using namespace std;
bool check(int n, int xs[], int k, int ss1[], int ss2[], int ans1[] = nullptr, int ans2[] = nullptr) {
  vector<int> ideal(n), idealrev(n), ys(n), ysrev(n);
  for (int i = 0; i < n; ++i)
    ideal[i] = idealrev[i] = ysrev[ys[i] = xs[i]] = i;
  for (int i = k-1; i >= 0; --i) {
    swap(ideal[ss1[i]], ideal[ss2[i]]);
    swap(idealrev[ideal[ss1[i]]], idealrev[ideal[ss2[i]]]);
  }
  int lst = 0;
  for (int i = 0; i < k; ++i) {
    swap(ideal[ss1[i]], ideal[ss2[i]]);
    swap(idealrev[ideal[ss1[i]]], idealrev[ideal[ss2[i]]]);
    swap(ys[ss1[i]], ys[ss2[i]]);
    swap(ysrev[ys[ss1[i]]], ysrev[ys[ss2[i]]]);
    // cerr << "-> " << lst << " " << idealrev[lst] << " " << ysrev[lst] << "\n";
    while (lst < n && idealrev[lst] == ysrev[lst]) ++lst;
    if (lst < n) {
      int a = ysrev[lst], b = idealrev[lst]; 
      swap(ys[a], ys[b]);
      swap(ysrev[ys[a]], ysrev[ys[b]]);
      if (ans1 != nullptr) { ans1[i] = a; ans2[i] = b; }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 20 / 20
• Subtask 6: 26 / 26