Submission #379608

#	Time	Username	Problem	Language	Result	Execution time	Memory
379608		idk321	Sorting (IOI15_sorting)	C++11	0 / 100	6 ms	620 KiB

sorting

#include "sorting.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 600005;
int n, m;
int* s;
int* x;
int* y;
int* q;
int* p;
int np[N];
int nq[N];


bool isOk(int r)
{
    for (int i = 0; i < m; i++)
    {
        p[i] = 0;
        q[i] = 0;
    }
    vector<int> change(n);
    for (int i = 0; i < n; i++) change[i] = i;
    for (int i = 0; i <= r; i++)
    {
        swap(change[x[i]], change[y[i]]);
    }
    vector<int> needed(n);
    for (int i = 0; i < n; i++)
    {
        needed[change[i]] = i;
    }

    vector<int> cur(s, s + n);

    vector<int> isOn(n);
    for (int i = 0; i < n; i++)
    {
        isOn[cur[i]] = i;
    }


    int check = 0;
    for (int i = 0; i <= r; i++)
    {
        swap(cur[x[i]], cur[y[i]]);
        swap(needed[x[i]], needed[y[i]]);
        isOn[cur[x[i]]] = x[i];
        isOn[cur[y[i]]] = y[i];


        while (check < n)
        {
            if (check != needed[isOn[check]])
            {
                int a = isOn[check];
                int b = isOn[needed[isOn[check]]];
                swap(cur[a], cur[b]);
                isOn[cur[a]] = a;
                isOn[cur[b]] = b;
                np[i] = a;
                nq[i] = b;
                break;
            }

            check++;
        }

        if (check == n)
        {
            np[i] = 0;
            nq[i] = 0;
        }
    }


    cout << r << endl;
    for (int i : cur) cout << i << " ";
    cout << endl;

    for (int i = 1; i < n; i++)
    {
        if (cur[i] < cur[i - 1]) return false;
    }
    return true;
}

int bs()
{
    int a = 0;
    int b = m - 1;
    int res = -1;

    while (a <= b)
    {
        int mid = (a + b) / 2;

        if (isOk(mid))
        {
            res = mid;
            b = mid - 1;
        } else
        {
            a = mid + 1;
        }
    }

    return res;
}


int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    n = N;
    m = M;
    s = S;
    x = X;
    y = Y;
    p = P;
    q = Q;

    bool alreadyGood = true;
    for (int i = 1; i < n; i++)
    {
        if (s[i] < s[i - 1]) alreadyGood = false;
    }

    if (alreadyGood) return 0;


    int best = bs() + 1;

    for (int i = 0; i < best; i++)
    {
        p[i] = np[i];
        q[i] = nq[i];
    }



	return best;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:115:76: warning: declaration of 'N' shadows a global declaration [-Wshadow]
  115 | int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
      |                                                                            ^
sorting.cpp:7:11: note: shadowed declaration is here
    7 | const int N = 600005;
      |           ^

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