oj.uz

답안 #432295

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
432295 2021-06-18T07:36:43 Z snasibov05 정렬하기 (IOI15_sorting) C++14
20 / 100
 1000 ms 76848 KB 
#include "sorting.h"
#include <vector>
#include <cassert>
#include <algorithm>

using namespace std;

#define pii pair<int, int>
#define f first
#define s second
#define pb push_back

int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {

    vector<vector<int>> v(m+1, vector<int>(n));
    vector<vector<int>> idx(m+1, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        v[0][i] = s[i];
        idx[0][s[i]] = i;
    }
    
    if (is_sorted(v[0].begin(), v[0].end())) return 0;

    for (int i = 1; i <= m; ++i) {
        p[i-1] = q[i-1] = 0;
        v[i] = v[i-1];
        idx[i] = idx[i-1];
        swap(idx[i][v[i][x[i-1]]], idx[i][v[i][y[i-1]]]);
        swap(v[i][x[i-1]], v[i][y[i-1]]);
    }

    vector<int> final = idx[m];
    vector<int> arr = v[m];
    vector<pii> swaps;

    for (int i = 0; i < n; ++i) {
        if (final[i] == i) continue;
        int k = final[i];
        swaps.pb({i, k});
        final[arr[i]] = k;
        arr[k] = arr[i];
        arr[i] = i;
    }

    assert(is_sorted(arr.begin(), arr.end()));

    arr = v[m];

    int k = swaps.size();
    for (int i = 1; i <= k; ++i){
        int a = idx[i][arr[swaps[i-1].f]];
        int b = idx[i][arr[swaps[i-1].s]];
        p[i-1] = a, q[i-1] = b;
        swap(idx[i][arr[swaps[i-1].f]], idx[i][arr[swaps[i-1].s]]);
        swap(v[i][a], v[i][b]);
        swap(arr[swaps[i-1].f], arr[swaps[i-1].s]);
        
        if (is_sorted(v[i].begin(), v[i].end())) return i;

        for (int j = i+1; j <= m; ++j) {
            v[j] = v[j-1];
            idx[j] = idx[j-1];
            swap(idx[j][v[j][x[j-1]]], idx[j][v[j][y[j-1]]]);
            swap(v[j][x[j-1]], v[j][y[j-1]]);
        }
    }

    assert(is_sorted(v[m].begin(), v[m].end()));

    return m;
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:49:23: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   49 |     int k = swaps.size();
      |             ~~~~~~~~~~^~

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 280 KB Output is correct
7 Correct 1 ms 280 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 280 KB Output is correct
7 Correct 1 ms 280 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 22 ms 2764 KB Output is correct
11 Correct 25 ms 2892 KB Output is correct
12 Correct 22 ms 2724 KB Output is correct

Subtask #3
0 / 16.0

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

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 280 KB Output is correct
7 Correct 1 ms 280 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 22 ms 2764 KB Output is correct
11 Correct 25 ms 2892 KB Output is correct
12 Correct 22 ms 2724 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Incorrect 20 ms 2636 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1077 ms 76848 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1077 ms 76848 KB Time limit exceeded
2 Halted 0 ms 0 KB -