299 - Train Swapping

[brianfry713]

If L is 0 there is probably a blank line after it, as "Each test case consists of two input lines."
You're not printing the period at the end of the line.

[ltanure]

I tested this code some many times. I can't get why is runtime error.
There is no way this could be wrong. I tested with the 299_input.zip that has 10000 inputs.

I always get this :

Hi,

This is an automated response from UVa Online Judge.

Your submission with number 13559676 for the problem 299 - Train Swapping has failed with verdict Runtime error.

This means that the execution of your program didn't finish properly. Remember to always terminate your code with the exit code 0.

Best regards,

The UVa Online Judge team

My code :

################################################
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <malloc.h>

#define MAX_LINE_SIZE 2500

typedef struct _node {
int x;
struct _node *next;
struct _node *previous;
} Node;
Node * root = NULL;
Node * tail = NULL;
int list_length = 0;


void free_list(){
Node * tmp = tail;
while(tmp != NULL){
tail = tmp->previous;
free(tmp);
tmp = tail;
list_length--;
}
root = NULL;
tail = NULL;
list_length = 0;
}

int is_ordened(){
Node * tmp = root;
while(tmp->next != NULL){
if(tmp->x > (tmp->next)->x){
return 0;
}
tmp = tmp->next;
}
return 1;
}

Node * find_max(int * pos){
Node * tmp = root;
Node * max_add = NULL;
int max = -1;
int position = 0;

while(tmp != NULL){
if(tmp->x > max){
max_add = tmp;
max = tmp->x;
(*pos) = position;
}
tmp = tmp->next;
position++;

}
return max_add;
}

void remove_number(Node * item){
if(item->next != NULL){
(item->next)->previous = item->previous;
} else {
tail = item->previous;
}
if(item->previous != NULL){
(item->previous)->next = item->next;
} else {
root = item->next;
}
free(item);
list_length--;
}

void add_number(int number){
Node * new = (Node *) malloc(sizeof(Node));
new->x = number;
new->next = NULL;
if(root == NULL){
root = new;
tail = new;
new->previous = NULL;
}else{
tail->next = new;
new->previous = tail;
tail = new;
}
list_length++;
}

int read_int_ptr(char * str, int * pos){
int number = 0;
while(str[*pos]!='\0' && str[*pos] != ' ' && str[*pos] != '\n'){
number = (number*10) + (str[*pos]-48);
(*pos)++;
}
(*pos)++;
return number;
}

int read_int(char * str){
int zero = 0;
return read_int_ptr(str,&zero);
}

void read_int_vet(char * str, int len){
int i= 0;
int pos = 0;
for(i=0;i<len;i++){
add_number(read_int_ptr(str,&pos));
}
}

int optimum_swaps(){
int pos = 0;
int swaps = 0;

while(list_length>0){
if(is_ordened()){break;}
Node * tmp = find_max(&pos);
swaps += list_length-(pos+1);
remove_number(tmp);
}
return swaps;
}

int main(){
char * ret;
char buffer[MAX_LINE_SIZE];
ret = fgets(buffer, MAX_LINE_SIZE, stdin);
int total_cases = read_int(buffer);
int len = 0;
int i = 0;
for(i=0;i<total_cases;i++){
ret = fgets(buffer, MAX_LINE_SIZE, stdin);
len = read_int(buffer);
ret = fgets(buffer, MAX_LINE_SIZE, stdin);
read_int_vet(buffer, len);
printf("Optimal train swapping takes %d swaps.\n",optimum_swaps());
free_list();
}
return(0);
}

[brianfry713]

It seems the input specification is wrong and you can't read line by line on this problem. Replace fgets with scanf and you'll get AC.

[ehsanulbigboss]

[brianfry713]

Next time post in the existing thread.
Your code doesn't match the sample I/O.

[SunNEET]

I used similar code to solve UVa 10810,11858,11495
I don't know why i keep getting RuntimeError in this problem
Have already tried the large input above(299_input.zip) and i got the same output with uDebug

Code: Select all

#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <climits>
#include <vector>
#include <set>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;
typedef vector<long long> vll;
ll Count;

vll merge(vll &vec,const vll& left,const vll& right)
{
    vll result ;
    ll left_it=0,right_it=0;
    while(left_it < left.size() && right_it < right.size()){
        if(left[left_it] > right[right_it]){
            result.push_back(right[right_it]);
            right_it++;
            Count += left.size() - left_it;
        }
        else{
            result.push_back(left[left_it]);
            left_it++;
        }
    }
    while(left_it<left.size()){
        result.push_back(left[left_it]);
        left_it++;
    }
    while(right_it<right.size()){
        result.push_back(right[right_it]);
        right_it++;
    }
    vec = result;
    return vec;
}

vll merge_sort(vll &vec)
{
    if(vec.size()==1)
        return vec;

    vll::iterator middle = vec.begin() + vec.size()/2;
    
    vll left(vec.begin(),middle);
    vll right(middle,vec.end());

    left = merge_sort(left);
    right = merge_sort(right);

    return merge(vec,left,right);
}




int main()
{
    //freopen("in","r",stdin);
    int N,n;
    scanf("%d",&N);
    while(N--){
        vll v;
        ll tmp;
        scanf("%d",&n);
        Count = 0;
        for(int i=0;i<n;i++){
            scanf("%lld",&tmp);
            v.push_back(tmp);
        }
        merge_sort(v);
        printf("Optimal train swapping takes %lld swaps.\n",Count);
    }
    return 0;
}

[risk1996]

Can anyone help me?
I've tried it twice and still getting WA.
I didn't forget to add the period and have tried to limit the train to 50.

Code: Select all

AC