제출 #763565

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
763565		Ahmed57	Sorting (IOI15_sorting)	C++17	100 / 100	188 ms	26968 KiB

sorting

#include <bits/stdc++.h>

using namespace std;
int vis[200001];
vector<int> vs;
vector<int> now;
void dfs(int i){
    vis[i] = 1;
    vs.push_back(i);
    if(!vis[now[i]])dfs(now[i]);
}
int findSwapPairs(int N,int S[],int M,int X[],int Y[],int P[],int Q[]){
    long long l = 0 , r = M , nah = 0;
    while(l<=r){
        long long mid = (l+r)/2;
        now.clear();
        for(int i = 0;i<N;i++)now.push_back(S[i]);
        for(int i = 0;i<mid;i++){
            swap(now[X[i]],now[Y[i]]);
        }
        memset(vis,0,sizeof vis);
        int ans = N;
        for(int i = 0;i<N;i++){
            if(!vis[i]){
                vs.clear();
                dfs(i);
                ans--;
            }
        }
        if(ans<=mid){
            r = mid-1;
            nah = mid;
        }else l = mid+1;
    }
    now.clear();
    for(int i = 0;i<N;i++)now.push_back(S[i]);
    for(int i = 0;i<nah;i++){
        swap(now[X[i]],now[Y[i]]);
    }
    memset(vis,0,sizeof vis);
    vector<pair<int,int>> swps;
    for(int i = 0;i<N;i++){
        if(!vis[i]){
            vs.clear();
            dfs(i);
            for(int xd = 1;xd<vs.size();xd++){
                swps.push_back({vs[0],vs[xd]});
            }
        }
    }
    reverse(swps.begin(),swps.end());
    int pos[N] = {0};
    now.clear();
    for(int i = 0;i<N;i++){
        now.push_back(S[i]);pos[S[i]] = i;
    }
    for(int i = 0;i<nah;i++){
        swap(S[X[i]],S[Y[i]]);
        swap(pos[S[X[i]]],pos[S[Y[i]]]);
        if(swps.empty()){
            P[i] = 0;
            Q[i] = 0;
        }else{
            P[i] = pos[swps.back().first];
            Q[i] = pos[swps.back().second];
            swps.pop_back();
        }
        //cout<<X[i]<<" "<<Y[i]<<" "<<P[i]<<" "<<Q[i]<<endl;
    }
    return nah;
}/*
int main(){
    int S[] ={3,0,4,2,1};
    int X[] = {1,4,2,1,0};
    int Y[] ={1,0,3,4,4};
    int P[] ={0,0,0,0,0};
    int Q[] = {0,0,0,0,0};
    findSwapPairs(5,S,5,X,Y,P,Q);
}
*/

컴파일 시 표준 에러 (stderr) 메시지

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:46:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |             for(int xd = 1;xd<vs.size();xd++){
      |                            ~~^~~~~~~~~~
sorting.cpp:70:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   70 |     return nah;
      |            ^~~

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 20 / 20
• Subtask 6: 26 / 26