oj.uz

Submission #307485

# Submission time Handle Problem Language Result Execution time Memory
307485 2020-09-28T10:25:24 Z lohacho Sorting (IOI15_sorting) C++14
0 / 100
 2 ms 512 KB 
#include "sorting.h"
#include <bits/stdc++.h>

using namespace std;

using LL = long long;
const int INF = (int)1e9 + 7;
const int NS = (int)2e5 + 4;
int mov[NS], Index[NS], pos[NS], S_save[NS], ba[NS];

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    for(int i = 0; i < N; ++i){
        S_save[i] = S[i];
    }
    int low = 0, high = N - 1, mid;
    function < int() > can_sort = [&](){
        for(int i = 0; i < N; ++i){
            S[i] = S_save[i];
            mov[i] = i; Index[S[i]] = i; ba[i] = S[i];
            pos[S[i]] = i;
        }
        for(int i = mid - 1; i >= 0; --i){
            swap(mov[X[i]], mov[Y[i]]);
        }
        int diff = 0;
        for(int i = 0; i < mid; ++i){
            while(diff < N && mov[diff] == S[diff]) ++diff;
            swap(Index[ba[X[i]]], Index[ba[Y[i]]]);
            swap(ba[X[i]], ba[Y[i]]);
            if(diff >= N){
                P[i] = Q[i] = 0;
            }
            else{
                P[i] = Index[S[diff]], Q[i] = Index[mov[diff]];
                swap(Index[S[diff]], Index[mov[diff]]);
                swap(ba[P[i]], ba[Q[i]]);
                swap(S[diff], S[pos[mov[diff]]]);
            }
        }
        while(diff < N && mov[diff] == S[diff]) ++diff;
        if(diff >= N) return 1;
        else return 0;
    };
    while(low < high){
        mid = (low + high) >> 1;
        for(int i = 0; i < N; ++i) P[i] = Q[i] = 0;
        if(can_sort()){
            high = mid;
        }
        else{
            low = mid + 1;
        }
    }
    return low;
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:11:39: warning: unused parameter 'M' [-Wunused-parameter]
   11 | int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
      |                                   ~~~~^

Subtask #1
0 / 8.0

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

Subtask #3
0 / 16.0

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