Submission #838374

#	Time	Username	Problem	Language	Result	Execution time	Memory
838374		AbdelmagedNour	Sorting (IOI15_sorting)	C++17	20 / 100	91 ms	19540 KiB

sorting

#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 (stderr)

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 / 8
• Subtask 2: 12 / 12
• Subtask 3: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 20
• Subtask 6: 0 / 26