제출 #379600

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
379600		idk321	정렬하기 (IOI15_sorting)	C++11	74 / 100	1093 ms	15940 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);

    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;
                p[i] = a;
                q[i] = b;
                break;
            }

            check++;
        }


    }



    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 best = -1;
    for (int i = 0; i < m; i++)
    {
        if (isOk(i))
        {
            best = i + 1;
            break;
        }
    }




	return best;
}

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