답안 #484621

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
484621	2021-11-04T19:53:55 Z	couplefire	정렬하기 (IOI15_sorting)	C++17	20 / 100	1 ms	460 KB

sorting

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

int findSwapPairs(int n, int arr[], int m, int x_moves[], int y_moves[], int x_ans[], int y_ans[]){
    vector<int> fin_arr(n), x_todo, y_todo;
    auto calc = [&](int mid)->int{
        x_todo.clear(); y_todo.clear();
        for(int i = 0; i<n; ++i) fin_arr[i] = arr[i];
        for(int i = 0; i<mid; ++i)
            swap(fin_arr[x_moves[i]], fin_arr[y_moves[i]]);
        for(int i = 0; i<n; ++i)
            while(fin_arr[i]!=i)
                x_todo.push_back(fin_arr[i]), y_todo.push_back(fin_arr[fin_arr[i]]), 
                swap(fin_arr[i], fin_arr[fin_arr[i]]);
        return (int)x_todo.size();
    };
    int lo = 0, hi = m;
    while(lo<hi){
        int mid = lo+(hi-lo)/2;
        if(calc(mid)<=mid) hi = mid;
        else lo = mid+1;
    } calc(lo);
    vector<int> pos(n);
    for(int i = 0; i<n; ++i)
        pos[arr[i]] = i;
    for(int i = 0; i<lo; ++i)
        swap(pos[arr[x_moves[i]]], pos[arr[y_moves[i]]]), swap(arr[x_moves[i]], arr[y_moves[i]]),
        x_ans[i] = pos[x_todo[i]], y_ans[i] = pos[y_todo[i]],
        swap(pos[arr[x_ans[i]]], pos[arr[y_ans[i]]]), swap(arr[x_ans[i]], arr[y_ans[i]]);
    return lo;
}

Subtask #1

8.0 / 8.0

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

Subtask #2

12.0 / 12.0

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

Subtask #3

0 / 16.0

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

Subtask #4

0 / 18.0

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

Subtask #5

0 / 20.0

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

Subtask #6

0 / 26.0

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