oj.uz

Submission #793916

# Submission time Handle Problem Language Result Execution time Memory
793916 2023-07-26T08:04:36 Z Jarif_Rahman Sorting (IOI15_sorting) C++17
20 / 100
 1 ms 340 KB 
#include "sorting.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

vector<pair<int, int>> get_swaps(vector<int> S){
    int n = S.size();
    vector<pair<int, int>> swaps;
    vector<int> pos(n);
    for(int i = 0; i < n; i++) pos[S[i]] = i;
    vector<bool> bl(n, 0);

    for(int i = 0; i < n; i++){
        if(bl[S[i]]) continue;
        if(S[i] == i){
            bl[i] = 1;
            continue;
        }
        int j = i;
        while(1){
            if(bl[S[j]]){
                bl[j] = 1;
                break;
            }
            swaps.pb({S[j], j});
            bl[j] = 1;
            j = S[j];
        }

    }

    return swaps;
}

int findSwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[]){
    bool sorted = 1;
    for(int i = 0; i < n; i++) sorted&=(S[i] == i);
    if(sorted) return 0;

    int k;
    
    vector<int> s(n);
    for(int i = 0; i < n; i++) s[i] = S[i];

    int a = 0, b = m-1;
    int ls = -1;
    while(a < b){
        int md = (a+b)/2;
        while(ls < md){
            ls++;
            swap(s[X[ls]], s[Y[ls]]);
        }
        while(ls > md){
            swap(s[X[ls]], s[Y[ls]]);
            ls--;
        }
        if(get_swaps(s).size() <= md+1) b = md;
        else a = md+1;
    }

    k = a;
    while(ls < ls){
        ls++;
        swap(s[X[ls]], s[Y[ls]]);
    }
    while(ls > ls){
        swap(s[X[ls]], s[Y[ls]]);
        ls--;
    }

    vector<int> pos(n);
    for(int i = 0; i < n; i++) pos[S[i]] = i;

    auto swaps = get_swaps(s);
    for(int i = 0; i <= k; i++){
        swap(S[X[i]], S[Y[i]]);
        swap(pos[S[X[i]]], pos[S[Y[i]]]);

        if(i >= swaps.size()) P[i] = 0, Q[i] = 0;
        else{
            auto [x, y] = swaps[i];
            swap(pos[x], pos[y]);
            swap(S[pos[x]], S[pos[y]]);
            P[i] = pos[x], Q[i] = pos[y];
        }
    }

    return k+1;
}

Compilation message

sorting.cpp: In function 'std::vector<std::pair<int, int> > get_swaps(std::vector<int>)':
sorting.cpp:11:19: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   11 |     int n = S.size();
      |             ~~~~~~^~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:61:32: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |         if(get_swaps(s).size() <= md+1) b = md;
      |            ~~~~~~~~~~~~~~~~~~~~^~~~~~~
sorting.cpp:66:14: warning: self-comparison always evaluates to false [-Wtautological-compare]
   66 |     while(ls < ls){
      |           ~~ ^ ~~
sorting.cpp:70:14: warning: self-comparison always evaluates to false [-Wtautological-compare]
   70 |     while(ls > ls){
      |           ~~ ^ ~~
sorting.cpp:83:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         if(i >= swaps.size()) P[i] = 0, Q[i] = 0;
      |            ~~^~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Incorrect 0 ms 212 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -