Submission #379598

#	Time	Username	Problem	Language	Result	Execution time	Memory
379598		idk321	Sorting (IOI15_sorting)	C++11	20 / 100	49 ms	492 KiB

sorting

#include "sorting.h"

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

int n, m;
int* s;
int* x;
int* y;
int* q;
int* p;

bool isOk(int r)
{
    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);

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

        for (int j = 0; j < n; j++)
        {
            if (needed[j] != cur[j])
            {
                for (int k = 0; k < n; k++)
                {
                    if (cur[k] == needed[j])
                    {
                        p[i] = k;
                        q[i] = j;
                        swap(cur[k], cur[j]);
                    }
                }
                break;
            }
        }
    }


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

int bs()
{
    int from = 0;
    int to = m - 1;
    int res = -1;

    while (from <= to)
    {
        int mid = (from + to) / 2;

        if (isOk(mid))
        {
            res = mid;
            to = mid - 1;
        } else
        {
            from = 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 r = bs();


	return r + 1;
}

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