Submission #401471

#	Time	Username	Problem	Language	Result	Execution time	Memory
401471		iulia13	Sorting (IOI15_sorting)	C++14	100 / 100	174 ms	16588 KiB

sorting

#include "sorting.h"
#include <iostream>


using namespace std;
const int N = 2e5;
int ss[N];
int poz[N];
int nr;
int pp[3 * N];
int qq[3 * N];
bool check(int n, int m, int s[], int x[], int y[])
{
    int i; nr = 0;
    for (i = 0; i < n; i++)
        ss[i] = s[i];
    for (i = 0; i < m; i++)
        swap(ss[x[i]], ss[y[i]]);
    for (i = 0; i < n; i++)
        poz[ss[i]] = i;
    for (i = 0; i < n; i++)
        if (ss[i] != i)
        {
            poz[ss[i]] = poz[i];
            ss[poz[i]] = ss[i];
            nr++;
            pp[nr - 1] = i;
            qq[nr - 1] = ss[i];
        }
    if (nr <= m)
    {
        for(i = nr; i < m; i++)
            pp[i] = qq[i] = 0;
        return true;
    }
    return false;
}
int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[])
{
    int i, ok = 1;
    for (i = 0; i < n && ok; i++)
        if (s[i] != i)
            ok = 0;
    if (ok)
        return 0;
    int st = 1, dr = m, sol;
    while (st <= dr)
    {
        int mid = (st + dr) / 2;
        if (check(n, mid, s, x, y))
            dr = mid - 1, sol = mid;
        else
            st = mid + 1;
    }
    check(n, sol, s, x, y);
    m = sol;
    for (i = 0; i < n; i++)
        poz[s[i]] = i;
    for (i = 0; i < m; i++)
    {
        swap(poz[s[x[i]]], poz[s[y[i]]]);
        swap(s[x[i]], s[y[i]]);
        p[i] = poz[pp[i]];
        q[i] = poz[qq[i]];
        swap(poz[s[p[i]]], poz[s[q[i]]]);
        swap(s[p[i]], s[q[i]]);
    }
    return m;
}/*
int s[N];
int x[N];
int y[N];
int p[N];
int q[N];

int main()
{
    int n, i, m;
    cin >> n;
    for (i = 0; i < n; i++)
        cin >> s[i];
    cin >> m;
    for (i = 0; i < n; i++)
        cin >> x[i] >> y[i];
    cout << findSwapPairs(n, s, m, x, y, p, q);
    return 0;
}*/

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:46:25: warning: 'sol' may be used uninitialized in this function [-Wmaybe-uninitialized]
   46 |     int st = 1, dr = m, sol;
      |                         ^~~

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