oj.uz

Submission #795703

# Submission time Handle Problem Language Result Execution time Memory
795703 2023-07-27T13:09:21 Z jasmin Sorting (IOI15_sorting) C++17
20 / 100
 1 ms 340 KB 
#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;

int cnt_cycle(vector<int>& s, int n){

    vector<bool> vis(n, false);
    int cnt=0;
    for(int v=0; v<n; v++){
        if(vis[v]) continue;
        
        cnt++;

        int mom=s[v];
        while(!vis[mom]){

            vis[mom]=true;
            mom=s[mom];
        }
    }

    return cnt;
}

int cnt_cycles(int rounds, vector<int>& s, int x[], int y[], int n){
    for(int i=0; i<rounds; i++){
        swap(s[x[i]], s[y[i]]);
    }

    int cnt=0;
    vector<bool> vis(n);
    for(int v=0; v<n; v++){
        if(!vis[v]) cnt++;

        while(!vis[v]){
            vis[v]=true;

            v=s[v];
        }
    }
    return cnt;
}

int findSwapPairs(int n, int S[], int m, int x[], int y[], int p[], int q[]) {
    
    //initialize
    vector<int> s(n);
    for(int i=0; i<n; i++){
        s[i] = S[i];
    }

    //cnt minimal rounds
    /*int rounds=-1;
    int cnt = n-cnt_cycle(s, n);
    for(int i=0; i<m; i++){

        if(cnt<=i){
            rounds = i;
            break;
        }

        swap(s[x[i]], s[y[i]]);
        cnt = n-cnt_cycle(s, n);
    }

    if(rounds==-1 && cnt<=m){
        rounds=m;
    }
    assert(rounds!=-1);*/

    int l=0; int r=m;
    int ans=m;
    while(l<=r){
        int mi=l+(r-l)/2;

        if(n-cnt_cycles(mi, s, x, y, n) <= mi){
            ans=mi;
            r=mi-1;
        }
        else{
            l=mi+1;
        }
    }
    int rounds=ans;

    for(int i=0; i<rounds; i++){
        swap(s[x[i]], s[y[i]]);
    }

    //find swaps
    deque<int> missing;
    vector<int> next(n);

    vector<bool> vis(n, false);
    for(int v=0; v<n; v++){
        if(vis[v]) continue;

        int mom = v;
        while(!vis[mom]){
            vis[mom]=true;

            missing.push_back(s[mom]);
            next[s[mom]] = s[s[mom]];

            mom=s[mom];
        }
        missing.pop_back(); //last in cycle doesn't need to be swapped anymore
    }

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

    for(int i=rounds-1; i>=0; i--){

        if(missing.empty()){

            p[i]=q[i]=0;
            continue;
        }

        int a=missing.front(); missing.pop_front();
        int b=next[a];

        //cout << a << " " << b << ": " << pos[a] << " " << pos[b] << "\n";

        p[i] = pos[a];
        q[i] = pos[b];

        swap(pos[s[x[i]]], pos[s[y[i]]]);
        swap(s[x[i]], s[y[i]]);
    }

    return rounds;
}

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 0 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 0 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 1 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 212 KB Output is correct
12 Correct 0 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 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 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 0 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 1 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 212 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 292 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 308 KB Output is correct
17 Incorrect 1 ms 340 KB Output isn't correct
18 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 -