Submission #1168926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168926		anmattroi	Sorting (IOI15_sorting)	C++17	54 / 100	7 ms	5468 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define maxn 200005
using namespace std;
using ii = pair<int, int>;

vector<int> Times[maxn];

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    int fl = 1;
    for (int i = 0; i < N; i++) if (S[i] != i) {fl = 0; break;}
    if (fl == 1) return 0;
    for (int i = 0; i < N; i++) Times[i].emplace_back(INT_MAX);

    for (int i = M-1; i >= 0; i--) {
        if (X[i] != Y[i]) {
            Times[X[i]].emplace_back(i);
            Times[Y[i]].emplace_back(i);
        }
    }


    for (int idx = 0; idx < M; idx++) {
        swap(S[X[idx]], S[Y[idx]]);
        P[idx] = Q[idx] = 0;
        int pos = -1, T = -1;
        for (int i = 0; i < N; i++)
        if (S[i] != i) {
            while (Times[i].back() <= idx) Times[i].pop_back();

            if (T < Times[i].back()) {
                T = Times[i].back();
                pos = i;
            }
        }
        if (pos == -1) return idx+1;
        int correct_pos = -1;
        for (int i = 0; i < N; i++)
        if (S[i] == pos) {
            correct_pos = i;
            break;
        }
        P[idx] = pos; Q[idx] = correct_pos;
        swap(S[P[idx]], S[Q[idx]]);


        int fl = 1;
        for (int i = 0; i < N; i++) if (S[i] != i) {fl = 0; break;}
        if (fl)
            return idx+1;
    }

}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:55:1: warning: control reaches end of non-void function [-Wreturn-type]
   55 | }
      | ^

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