Submission #579962

#	Time	Username	Problem	Language	Result	Execution time	Memory
579962		AugustinasJucas	Sorting (IOI15_sorting)	C++14	0 / 100	2 ms	828 KiB

sorting

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

int n; int m;
vector<int> mas;
vector<pair<int, int> > swaps;

vector<int> simuliuok(int kiek) {
    vector<int> ret(n);
    for(int i = 0; i < n; i++) ret[i] = i;
    for(int i = 0; i < kiek; i++) {
        swap(ret[swaps[i].first], ret[swaps[i].second]);
    }
    return ret;
}
vector<int> iKuriaLekstutePerkelti(int kiek){
    vector<int> kurAtsidurs = simuliuok(kiek);
    vector<int> kuriLekstuteCiaAtsidurs(kiek);
    for(int i = 0; i < n; i++) {
        kuriLekstuteCiaAtsidurs[kurAtsidurs[i]] = i;
    }
    vector<int> kurEisiu (n);
    for(int i = 0; i < n; i++) {
        kurEisiu[i] = kuriLekstuteCiaAtsidurs[mas[i]];
    }
    return kurEisiu;
}

bool f(int kiek) {
    vector<int> kurEisiu = iKuriaLekstutePerkelti(kiek);
    vector<bool> vis(n, false);
    int s = 0;
    for(int i = 0; i < n; i++) {
        if(vis[i]) continue;
        for(int j = kurEisiu[i]; j != i; j = kurEisiu[j]) {
            vis[j] = true;
            s++;
        }
        vis[i] = true;
    }
    return s <= kiek;
}
vector<pair<int, int> > raskEiliskuma(vector<int> kurEisiu) {
    vector<bool> vis(n, false);
    vector<pair<int, int> > ret;
    for(int i = 0; i < n; i++) {
        if(vis[i]) continue;
        vis[i] = true;
        vector<int> ratas = {i};
        for(int j = kurEisiu[i]; j != i; j = kurEisiu[j]) {
            ratas.push_back(j);
            vis[j] = true;
        }
        for(int i = ratas.size() - 1; i > 0; i--) {
            ret.push_back({ratas[i], ratas[i-1]});
        }
    }
    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++) {
        mas.push_back(S[i]);
    }
    for(int i = 0; i < m; i++) {
        swaps.push_back({X[i], Y[i]});
    }
    int ans;
    int l = 0; int r = m; int mid;
    while(l <= r) {
        mid = (l + r) / 2;
        if(f(mid)) {
            ans = mid;
            r = mid-1;
        }else {
            l = mid+1;
        }
    }

    vector<int> kurEisiu = iKuriaLekstutePerkelti(ans);
    vector<pair<int, int> > eiliskumas = raskEiliskuma(kurEisiu);

    vector<int> lekstute(n), kurLekstute(n);
    for(int i = 0; i < n; i++) lekstute[i] = i, kurLekstute[i] = i;

    for(int i = 0; i < ans; i++) {

        kurLekstute[lekstute[X[i]]] = Y[i];
        kurLekstute[lekstute[Y[i]]] = X[i];
        swap(lekstute[X[i]], lekstute[Y[i]]);

        int A = eiliskumas[i].first;
        int B = eiliskumas[i].second;
        P[i] = kurLekstute[A];
        Q[i] = kurLekstute[B];
    }
    
    return ans;
}

Compilation message (stderr)

sorting.cpp: In function 'std::vector<std::pair<int, int> > raskEiliskuma(std::vector<int>)':
sorting.cpp:55:17: warning: declaration of 'i' shadows a previous local [-Wshadow]
   55 |         for(int i = ratas.size() - 1; i > 0; i--) {
      |                 ^
sorting.cpp:47:13: note: shadowed declaration is here
   47 |     for(int i = 0; i < n; i++) {
      |             ^
sorting.cpp:55:34: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   55 |         for(int i = ratas.size() - 1; i > 0; i--) {
      |                     ~~~~~~~~~~~~~^~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:69:9: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   69 |     int ans;
      |         ^~~

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