Triple Sort (TRPLSRT) - CodeChef May Challenge 2020 Solution

Here s a video solution with an explanation of the code

``````#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
using namespace std;

int n, k;
int nums[200001];
bool visited[200001];

void solve(int t){
vector<pair<int, int>> doub;

cin >> n >> k;
for(int i=0; i<=n; i++){
cin >> nums[i];
}
for(int i=1; i<=n; i++){
visited[i]=false;
}
vector<int> cycle;
for(int i=1; i<=n; i++){
if(!visited[i]){
int j=i;
while(!visited[j]){
visited[j]=true;
cycle.push_back(j);
j=nums[j];
}
}
while(cycle.size()>2){
int z=cycle.back();
cycle.pop_back();
int y = cycle.back();
cycle.pop_back();
int x=cycle.back();
if(cycle.size()==1){
cycle.pop_back();
k--;
}
}
if(cycle.size()==2){
doub.push_back(make_pair(cycle[0], cycle[1]));
}
}
while(doub.size()>1){
pair<int, int> one = doub.back();
doub.pop_back();
pair<int, int> two = doub.back();
doub.pop_back();
k-=2;
}
if(!doub.empty()){
cout << "-1" << endl;
}
if(k>=0){
}
}
return;
}

int main(){
int tests;
cin >> tests;
for(int i=0; i<tests; i++){
solve(i);
}
return 0;
}
``````
3 Likes

This does not even pass subtask 1.
The first and most obvious bug is when you check cycle.size() == 1.
There should NOT be a curly braces â€ś{ }â€ť after that because as the code is now the â€śanswer.push_backâ€ť will not execute unless cycle size is 1.

1 Like

change this to

``````if(cycle.size()==1)
cycle.pop_back();