oj.uz

Submission #401470

# Submission time Handle Problem Language Result Execution time Memory
401470 2021-05-10T10:40:54 Z iulia13 Sorting (IOI15_sorting) C++14
0 / 100
 2 ms 448 KB 
#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]]);
    }
    if (p[m - 1] == q[m - 1])
        return 2 * m - 1;
    return 2 * 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

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
0 / 8.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 20.0

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

Subtask #6
0 / 26.0

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