Submission #103523

#	Time	Username	Problem	Language	Result	Execution time	Memory
103523		Osama_Alkhodairy	Sorting (IOI15_sorting)	C++17	100 / 100	733 ms	31312 KiB

sorting

#include <bits/stdc++.h>
#include "sorting.h"
//#include "grader.cpp"
using namespace std;

int n, m;
vector <int> s;
vector <pair <int, int> > w;

vector <pair <int, int> > swaps(vector <int> &a){
    vector <bool> vis(n);
    vector <pair <int, int> > swaps;
    for(int i = 0 ; i < n ; i++){
        if(vis[i]) continue;
        vector <int> cycle;
        int cur = i;
        while(vis[cur] == 0){
            cycle.push_back(cur);
            vis[cur] = 1;
            cur = a[cur];
        }
        for(int i = 1 ; i < (int)cycle.size() ; i++){
            swaps.emplace_back(cycle[0], cycle[i]);
        }
    }
    vector <int> b = a;
    vector <pair <int, int> > ret;
    for(auto &i : swaps){
        ret.emplace_back(b[i.first], b[i.second]);
        swap(b[i.first], b[i.second]);
    }
    return ret;
}
vector <pair <int, int> > check(int mid){
    vector <int> a = s;
    for(int i = 0 ; i < mid ; i++){
        swap(a[w[i].first], a[w[i].second]);
    }
    auto c = swaps(a);
    if((int)c.size() > mid){
        return vector <pair <int, int> >(1, make_pair(-1, -1));
    }
    a = s;
    vector <int> pos(n);
    for(int i = 0 ; i < n ; i++){
        pos[a[i]] = i;
    }
    auto adjust = [&](int idx){
        pos[a[idx]] = idx;
    };
    vector <pair <int, int> > ret;
    for(int i = 0 ; i < mid ; i++){
        swap(a[w[i].first], a[w[i].second]);
        adjust(w[i].first);
        adjust(w[i].second);
        if(i >= (int)c.size()) ret.emplace_back(0, 0);
        else{
            ret.emplace_back(pos[c[i].first], pos[c[i].second]);
            swap(a[pos[c[i].first]], a[pos[c[i].second]]);
            adjust(pos[c[i].first]);
            adjust(pos[c[i].second]);
        }
    }
    return ret;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    n = N;
    m = M;
    for(int i = 0 ; i < n ; i++)
        s.push_back(S[i]);
    for(int i = 0 ; i < m ; i++)
        w.emplace_back(X[i], Y[i]);
    int l = 0, r = m;
    while(l <= r){
        int mid = (l + r) / 2;
        auto c = check(mid);
        if(c.size() == 0 || c[0].first != -1) r = mid - 1;
        else l = mid + 1;
    }
    r++;
    if(r == 0) return 0;
    auto ans = check(r);
    int sz = ans.size();
    for(int i = 0 ; i < sz ; i++){
        P[i] = ans[i].first;
        Q[i] = ans[i].second;
    }
	return sz;
}

Compilation message (stderr)

sorting.cpp: In function 'std::vector<std::pair<int, int> > swaps(std::vector<int>&)':
sorting.cpp:22:17: warning: declaration of 'i' shadows a previous local [-Wshadow]
         for(int i = 1 ; i < (int)cycle.size() ; i++){
                 ^
sorting.cpp:13:13: note: shadowed declaration is here
     for(int i = 0 ; i < n ; i++){
             ^
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:83:22: warning: conversion to 'int' from 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' may alter its value [-Wconversion]
     int sz = ans.size();
              ~~~~~~~~^~

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