oj.uz

Submission #838374

# Submission time Handle Problem Language Result Execution time Memory
838374 2023-08-26T17:57:48 Z AbdelmagedNour Sorting (IOI15_sorting) C++17
20 / 100
 91 ms 19540 KB 
#include <bits/stdc++.h>
using namespace std;
//#include "grader.cpp"
#include "sorting.h"
bool check(int T,int N,int M,int S[],int X[],int Y[],int P[],int Q[]){
    vector<vector<int>>nxt(T+1,vector<int>(N));
    for(int i=0;i<N;i++)nxt[T][i]=i;
    for(int i=T-1;i>=0;i--){
        for(int j=0;j<N;j++){
            nxt[i][j]=nxt[i+1][j];
        }
        swap(nxt[i][X[i]],nxt[i][Y[i]]);
    }
    int a[N];
    for(int i=0;i<N;i++)a[i]=S[i];
    for(int i=0;i<T;i++){
        int j=0;
        swap(a[X[i]],a[Y[i]]);
        while(j<N&&a[j]==nxt[i+1][j])j++;
        if(j==N)P[i]=Q[i]=0;
        else P[i]=j,Q[i]=find(nxt[i+1].begin(),nxt[i+1].end(),a[j])-nxt[i+1].begin();
        swap(a[P[i]],a[Q[i]]);
    }
    return is_sorted(a,a+N);
}
int findSwapPairs(int N,int S[],int M,int X[],int Y[],int P[],int Q[]){
    int l=1,r=M,res=1;
    if(is_sorted(S,S+N))return 0;
    while(l<=r){
        int md=(l+r)>>1;
        if(check(md,N,M,S,X,Y,P,Q))r=(res=md)-1;
        else l=md+1;
    }
    return res;
}

Compilation message

sorting.cpp: In function 'bool check(int, int, int, int*, int*, int*, int*, int*)':
sorting.cpp:21:68: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   21 |         else P[i]=j,Q[i]=find(nxt[i+1].begin(),nxt[i+1].end(),a[j])-nxt[i+1].begin();
      |                          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
sorting.cpp:5:28: warning: unused parameter 'M' [-Wunused-parameter]
    5 | bool check(int T,int N,int M,int S[],int X[],int Y[],int P[],int Q[]){
      |                        ~~~~^

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

Subtask #5
0 / 20.0

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

Subtask #6
0 / 26.0

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