Submission #580008

#	Time	Username	Problem	Language	Result	Execution time	Memory
580008		AugustinasJucas	Sorting (IOI15_sorting)	C++14	100 / 100	165 ms	30160 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> kuriLekstuteCiaAtsidurs = simuliuok(kiek);
  //  cout << "simluliantas: "; for(auto &x : kuriLekstuteCiaAtsidurs) cout << x << " ";
  //  cout << endl;
    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;
        }
     //   cout << "ratas: "; for(auto &x : ratas) cout << x << " ";
   //     cout << endl;
        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);
 //   cout << "kurEisiu: "; for(auto &x : kurEisiu) cout << x << " ";
 //   cout << endl << "eiliskumas: " << endl;
 //   for(auto &x : eiliskumas) {
 //       cout << "swp " << x.first << " lekstutes turini su " << x.second << " lekstutes turiniu" << endl;
  //  }
    vector<int> lekstute(n), kurLekstute(n);
    for(int i = 0; i < n; i++) lekstute[i] = i, kurLekstute[i] = i;
    //cout << endl;
    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, B;
        if(i >= eiliskumas.size()) A = B = 0;
        else {
            A = eiliskumas[i].first;
            B = eiliskumas[i].second;
        }
        P[i] = kurLekstute[A];
        Q[i] = kurLekstute[B];
        //cout << "swap " << X[i] << " su " << Y[i] << ". Tada lekstutes issidesciusios taip:";
       // for(auto x : lekstute) cout << x << " "; cout << endl;
        //cout << "tada swapinsiu lekstutes " << A << " turini su lekstutes " << B << " turiniu " << endl;
        //cout << "T.y., swap " << P[i] << " su " << Q[i] << endl << endl;
    }

    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:45:13: note: shadowed declaration is here
   45 |     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:98:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         if(i >= eiliskumas.size()) A = B = 0;
      |            ~~^~~~~~~~~~~~~~~~~~~~
sorting.cpp:69:9: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   69 |     int ans;
      |         ^~~

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