oj.uz

답안 #379611

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
379611 2021-03-18T20:08:36 Z idk321 정렬하기 (IOI15_sorting) C++11
20 / 100
 3 ms 492 KB 
#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 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();
    isOk(best);



	return best + 1;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 0 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Incorrect 0 ms 364 KB Output isn't correct

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 0 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 0 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Incorrect 0 ms 364 KB Output isn't correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 492 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Incorrect 2 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 492 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Incorrect 2 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -