Hello All
I have tried testing my program using boundary test data and the test data given in the problem statement, all of them are working fine. However, I get WA on submission, I must have done something wrong just cannot figure out how. It would be really nice if any one could suggest test case(s) that breaks my code, I guess I would be then able to figure out the flaw. I have included the code. Thanks in advance.
#include <iostream>
#include <vector>
using namespace std;
struct Color{
int color, priority;
};
struct Card {
Color *color;
int value;
bool operator > (const Card& c) const {
if (color != c.color) return color->priority > c.color->priority;
return value > c.value;
}
};
class Mcards {
private:
int maxlis;
int permute(Color colors[], Card cards[], int n, int totalCards) {
if (n == 1) {
return lis(cards, totalCards);
}
for (int i = 0; i < n; i++) {
swap(colors, i, n - 1);
maxlis = max(permute(colors, cards, n - 1, totalCards), maxlis);
swap(colors, i, n - 1);
}
return maxlis;
}
void swap(Color colors[], int i, int j) {
int priority = colors[i].priority;
colors[i].priority = colors[j].priority;
colors[j].priority = priority;
}
int lis(Card cards[], int totalCards) {
vector<int> q(totalCards, 1);
for (int k = 0; k < totalCards; k++) {
for (int j = 0; j < k; j++) {
if (cards[k] > cards[j] && q[k] < q[j] + 1) {
q[k] = q[j] + 1;
}
}
}
int max = 0;
for (int k = 0; k < totalCards; k++) {
if (q[k] > max) {
max = q[k];
}
}
return max;
}
public:
static void main() {
int C, N;
scanf("%d %d",&C, &N);
int totalCards = C * N;
Color *colors = new Color[C];
for (int i = 0; i < C; i++) {
Color color = {i + 1, i + 1};
colors[i] = color;
}
Card *cards = new Card[totalCards];
for (int i = 0, c, v; i < totalCards; i++) {
scanf("%d %d",&c, &v);
Card card = {colors + (c - 1), v};
cards[i] = card;
}
Mcards mcards;
int leastMoves = totalCards - mcards.permute(colors, cards, C, totalCards);
printf("%d\n", leastMoves);
}
};
int main() {
Mcards::main();
return 0;
}