Hello,
I am new to SPOJ, and I am still getting used to the SPOJ system. I have just solved my first problem ("8786. The Longest Chain of Domino Tiles") and wanted to check the differences in size and speed amongst C,C++,C#, and of cource just test myself how much time it takes me to write simple program in each language.
Unfortunately the C++ code gives "wrong answer". I have tested it locally by unit tests of my own and cannot find any problem with the code. The funny thing is that C code passed to the C++ compiler gives accepted solution so I assume there is some problem with STL which I have to avoid in solutions to SPOJ problems but I cannot figure out what is it.
Can you help me identify which C++/STL code does not work in SPOJ engine?
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
struct domino_tile
{
char start;
char end;
int size;
int used;
};
bool domino_compare(const domino_tile &elem1, const domino_tile &elem2)
{
int ret;
if(elem1.size < elem2.size)
{
ret = 1;
}
else
{
if(elem1.start < elem2.start)
ret = 1;
else if(elem1.start == elem2.start)
{
if(elem1.end == elem2.end)
ret = 0;
else
ret = 1;
}
}
return !ret;
}
bool find_next(std::vector<domino_tile> &data, char c, int &out_size)
{
std::vector<domino_tile>::iterator it;
for(it = data.begin(); it != data.end(); ++it)
{
if(!it->used)
{
if(it->start == c)
{
it->used = 1;
out_size = it->size;
break;
}
}
}
if(it == data.end())
return 0;
return 1;
}
//void print_tile(domino_tile &data)
//{
// std::cout << data.start << ".." << data.end << " " << data.size << " " << data.used << std::endl;
//}
int main()
{
int number = 0;
std::cin >> number;
std::vector<domino_tile> domino;
while(number--)
{
std::string tile;
std::cin >> tile;
domino_tile t;
t.size = tile.size();
t.start = tile[0];
t.end = tile[tile.size() -1];
t.used = 0;
domino.push_back(t);
}
/*std::cout << "--------" << std::endl;
std::for_each(domino.begin(), domino.end(), print_tile);*/
sort(domino.begin(), domino.end(), domino_compare);
/*std::cout << "--------" << std::endl;
std::for_each(domino.begin(), domino.end(), print_tile);*/
int startB, startC, resultB, resultC, resultBB, resultCC;
startB=startC=resultB=resultC=resultBB=resultCC=0;
std::vector<domino_tile>::iterator it;
for(it = domino.begin(); it != domino.end(); ++it)
{
if(it->start == 'B')
{
if(it->end == 'C')
{
startB++;
resultB += it->size;
}
else
{
it->used = 1;
resultBB += it->size;
}
}
else if(it->start == 'C')
{
if(it->end == 'B')
{
startC++;
resultC += it->size;
}
else
{
it->used =1;
resultCC += it->size;
}
}
}
if(startB == startC)
{
int result;
if(resultB > 0)
result = resultB + resultC + resultBB + resultCC;
else if(resultBB > resultCC)
result = resultBB;
else
result = resultCC;
std::cout << result << std::endl;
return 0;
}
char start_square;
char end_square;
int result = 0;
if(startB > startC)
{
start_square = 'B';
end_square = 'C';
}
else
{
start_square = 'C';
end_square = 'B';
}
while(1)
{
int v;
if(!find_next(domino, start_square, v))
break;
result += v;
if(!find_next(domino, end_square, v))
break;
result += v;
}
result += resultBB;
result += resultCC;
/*std::cout << "--------" << std::endl;
std::for_each(domino.begin(), domino.end(), print_tile);*/
std::cout << result << std::endl;
return 0;
}
And here is nearly identical code in C# which gives "accepted" answer:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace cs_proj
{
class domino_tile
{
public char start;
public char end;
public int size;
public bool used;
public override string ToString()
{
return start + ".." + end + " " + size + " " + used;
}
}
class domino01
{
private static int compare_domino_tiles(domino_tile l, domino_tile r)
{
int ret;
if (l.start < r.start)
ret = -1;
else if (l.start == r.start)
{
if (l.size < r.size)
ret = -1;
else if (l.size == r.size)
ret = 0;
else
ret = 1;
}
else
ret = 1;
return -ret;
}
private static bool find_next(List<domino_tile> data, char c, out int size)
{
size = 0;
for (int i = 0; i < data.Count; i++)
{
var d = data[i];
if (!d.used)
{
if (d.start == c)
{
d.used = true;
size = d.size;
return true;
}
}
}
return false;
}
static void Main(string[] args)
{
int number;
if(!Int32.TryParse(Console.ReadLine(), out number))
return;
List<domino_tile> domino = new List<domino_tile>(number);
while(number-- > 0)
{
string s = Console.ReadLine();
domino.Add(new domino_tile() {size = s.Length, used = false, start = s[0], end = s[s.Length -1]});
}
//foreach (var d in domino)
// Console.WriteLine(d);
domino.Sort(compare_domino_tiles);
//foreach (var d in domino)
// Console.WriteLine(d);
int startB, startC, resultB, resultC, resultBB, resultCC;
startB = startC = resultB = resultC = resultBB = resultCC = 0;
for(int i=0; i< domino.Count; i++ )
{
var d = domino[i];
if (d.start == 'B')
{
if (d.end == 'C')
{
startB++;
resultB += d.size;
}
else
{
d.used = true;
resultBB += d.size;
}
}
else
if (d.start == 'C')
{
if (d.end == 'B')
{
startC++;
resultC += d.size;
}
else
{
d.used = true;
resultCC += d.size;
}
}
}
int result = 0;
if (startB == startC)
{
if (startB > 0)
{
result = resultB + resultC + resultBB + resultCC;
}
else if (resultBB > resultCC)
result = resultBB;
else
result = resultCC;
Console.WriteLine(result);
return;
}
char start_char;
char end_char;
if (startB > startC)
{
start_char = 'B';
end_char = 'C';
}
else
{
start_char = 'C';
end_char = 'B';
}
while (true)
{
int v;
if (!find_next(domino, start_char, out v))
break;
result += v;
if (!find_next(domino, end_char, out v))
break;
result += v;
}
result += resultBB;
result += resultCC;
//foreach (var d in domino)
// Console.WriteLine(d);
Console.WriteLine(result);
return;
}
}
}
Thanks!
