oj.uz

Submission #854000

# Submission time Handle Problem Language Result Execution time Memory
854000 2023-09-25T19:26:34 Z abcvuitunggio Sorting (IOI15_sorting) C++17
16 / 100
 1 ms 452 KB 
#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
int vis[200001],pos[200001];
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]){
    bool ch=1;
    for (int i=0;i<N;i++)
        ch&=(S[i]==i);
    if (ch)
        return 0;
    int l=0,r=M-1,kq=-1;
    while (l<=r){
        int mid=(l+r)>>1;
        for (int i=0;i<=mid;i++)
            swap(S[X[i]],S[Y[i]]);
        for (int i=0;i<N;i++)
            vis[i]=0;
        int cnt=N;
        for (int i=0;i<N;i++)
            if (!vis[i]){
                cnt--;
                int j=i;
                while (!vis[j]){
                    vis[j]=1;
                    j=S[j];
                }
            }
        for (int i=mid;i>=0;i--)
            swap(S[X[i]],S[Y[i]]);
        if (cnt<=mid){
            kq=mid;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    for (int i=0;i<=kq;i++)
        swap(S[X[i]],S[Y[i]]);
    int id=0;
    for (int i=0;i<N;i++){
        while (i!=S[i]){
            P[id]=i;
            Q[id]=S[i];
            swap(S[i],S[S[i]]);
            id++;
        }
        pos[i]=i;
    }
    for (int i=id;i<=kq;i++)
        P[i]=Q[i]=0;
    for (int i=kq;i>=0;i--){
        P[i]=S[P[i]];
        Q[i]=S[Q[i]];
        swap(S[pos[X[i]]],S[pos[Y[i]]]);
        swap(pos[X[i]],pos[Y[i]]);
    }
    return kq+1;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 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 348 KB Output isn't correct
2 Halted 0 ms 0 KB -