Submission #778322

#	Time	Username	Problem	Language	Result	Execution time	Memory
778322		danikoynov	Sorting (IOI15_sorting)	C++14	20 / 100	9 ms	340 KiB

sorting

#include "sorting.h"
#include<bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 10;
int n, arr[maxn], used[maxn];
vector < pair < int, int > > edges;
int count_steps()
{
    for (int i = 0; i < n; i ++)
        used[i] = 0;
    int ans = 0;
    for (int i = 0; i < n; i ++)
    {
        if (used[i])
            continue;
        int v = arr[i], cnt = 0;
        while(v != i)
        {
            used[v] = 1;
            cnt ++;
            v = arr[v];
        }
        used[v] = 1;
        cnt ++;
        ans = ans + (cnt - 1);
    }
    return ans;
}

void build_edges()
{
    for (int i = 0; i < n; i ++)
        used[i] = 0;
    for (int i = 0; i < n; i ++)
    {
        if (used[i])
            continue;
        vector < int > ord;
        int v = arr[i];
        while(v != i)
        {
            ord.push_back(v);
            used[v] = 1;
            v = arr[v];
        }
        ord.push_back(i);
        used[i] = 1;

        for (int i = 0; i < ord.size() - 1; i ++)
            edges.push_back({arr[ord[i]], arr[ord[i + 1]]});
    }
}

int pos[maxn];
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
    n = N;
    bool sorted = true;
    for (int i = 0; i < N; i ++)
        if (S[i] != i)
            sorted = false;

    if (sorted)
        return 0;
    for (int i = 0; i < N; i ++)
        arr[i] = S[i];

    int pivot = -1;
    for (int i = 0; i < N; i ++)
    {
        swap(arr[X[i]], arr[Y[i]]);
        int steps = count_steps();
        /**cout << "--------------" << endl;
        for (int j = 0; j < N; j ++)
            cout << arr[j] << " ";
        cout << endl;
        cout << steps << endl;*/
        if (steps <= i + 1)
        {
            pivot = i;
            break;
        }
    }
    ///cout << pivot << endl;
    ///exit(0);
    build_edges();
    for (int i = 0; i < n; i ++)
        pos[S[i]] = i;
    for (int i = 0; i < edges.size(); i ++)
    {
        ///cout << edges[i].first << " : " << edges[i].second << endl;
        P[i] = pos[edges[i].first];
        Q[i] = pos[edges[i].second];
        swap(pos[edges[i].first], pos[edges[i].second]);
        int id1 = 0, id2 = 0;
        while(pos[id1] != X[i])
            id1 ++;
        while(pos[id2] != Y[i])
            id2 ++;
            ///cout << id1 << " : " << id2 << endl;
        swap(pos[id1], pos[id2]);
        ///swap(pos[X[i]], pos[Y[i]]);
    }
    for (int i = edges.size(); i <= pivot; i ++)
        P[i] = Q[i] = 0;
    return pivot + 1;
}

Compilation message (stderr)

sorting.cpp: In function 'void build_edges()':
sorting.cpp:51:18: warning: declaration of 'i' shadows a previous local [-Wshadow]
   51 |         for (int i = 0; i < ord.size() - 1; i ++)
      |                  ^
sorting.cpp:36:14: note: shadowed declaration is here
   36 |     for (int i = 0; i < n; i ++)
      |              ^
sorting.cpp:51:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for (int i = 0; i < ord.size() - 1; i ++)
      |                         ~~^~~~~~~~~~~~~~~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:91:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for (int i = 0; i < edges.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~
sorting.cpp:106:28: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  106 |     for (int i = edges.size(); i <= pivot; i ++)
      |                  ~~~~~~~~~~^~
sorting.cpp:57:39: warning: unused parameter 'M' [-Wunused-parameter]
   57 | int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
      |                                   ~~~~^

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