Y did I get a WA #2 ? Please help me !
Послано
BingoX 20 сен 2010 20:05
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int a[501][3], f[501], trace[501], n, ans, t;
void sort(int l, int r) {
int x = a[(l + r) >> 1][0];
int i, j, t[3];
i = l;
j = r;
do {
while (a[i][0] < x)
i++;
while (a[j][0] > x)
j--;
if (i <= j) {
memcpy(t, a[i], sizeof(t));
memcpy(a[i], a[j], sizeof(t));
memcpy(a[j], t, sizeof(t));
}
i++;
j--;
} while (i <= j);
if (i < r)
sort(i, r);
if (l < j)
sort(l, j);
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d %d", &a[i][0], &a[i][1]);
a[i][2] = i;
}
for (int i = 1; i <= n; i++)
f[i] = 1;
sort(1, n);
for (int i = 2; i <= n; i++)
for (int j = 1; j < i; j++)
if ((a[j][0] < a[i][0]) && (a[j][1] > a[i][1]) && (f[j] + 1 > f[i])) {
f[i] = f[j] + 1;
trace[i] = j;
}
ans = 0;
t = 0;
for (int i = 1; i <= n; i++)
if (f[i] > ans) {
ans = f[i];
t = i;
};
printf("%d\n", ans);
while (t != 0) {
printf("%d ", a[t][2]);
t = trace[t];
}
return 0;
}