1016 : please give me some test data that make my program fail
#include <stdio.h>
class heap {
private:
int *v;
int *d;
int *p;
int size;
private:
int parent(int index);
int left(int index);
int right(int index);
int cmp(int a, int b);
void swap(int a, int b);
void up(int index);
void down(int index);
public:
~heap();
heap(int v[], int size);
int extract();
void update(int index, int value);
};
int heap :: cmp(int a, int b) {
return (v[d[b]]==-1 || v[d[a]]<v[d[b]])&&v[d[a]]!=-1;
}
void heap :: swap(int a, int b) {
d[a]^=d[b]^=d[a]^=d[b];
p[d[a]]=a;
p[d[b]]=b;
}
int heap :: parent(int index) {
return (index-1)>>1;
}
int heap :: left(int index) {
return (index<<1)+1;
}
int heap :: right(int index) {
return (index<<1)+2;
}
void heap :: up(int index) {
while (index>0 && cmp(index,parent(index))) {
swap(index,parent(index));
index=parent(index);
}
}
void heap :: down(int index) {
int con;
do {
con=0;
if (right(index)<size) {
if (cmp(left(index), right(index))) {
if (cmp(left(index), index)) {
swap(left(index), index);
index=left(index);
con=1;
}
}
else if (cmp(right(index), index)) {
swap(right(index), index);
index=right(index);
con=1;
}
}
else if (left(index)<size) {
if (cmp(left(index), index)) {
swap(left(index), index);
index=left(index);
con=1;
}
}
} while (con);
}
heap :: heap(int v[], int size) {
this->size=size;
this->v=v;
d=new int[size];
p=new int[size];
for (int i=0; i<size; i++) {
v[i]=-1;
d[i]=i;
p[i]=i;
}
}
heap :: ~heap() {
if (d!=NULL)
delete d;
if (p!=NULL)
delete p;
}
void heap :: update(int index, int value) {
v[index]=value;
up(p[index]);
down(p[index]);
}
int heap :: extract() {
int toreturn;
if (size==0||v[d[0]]==-1) {
return -1;
}
else {
toreturn=d[0];
swap(0,size-1);
size--;
down(0);
return toreturn;
}
}
int main() {
#ifndef ONLINE_JUDGE
FILE *fi=fopen("1016.in","r");
FILE* fo=fopen("1016.out","w");
#else
FILE *fi=stdin;
FILE *fo=stdout;
#endif
const int width=8;
const int side[6][4]={{2,3,4,5},{2,5,4,3},{1,3,0,5},{1,4,0,2},{0,3,1,5},
{2,0,4,1}};
const int opposite[6]={1,0,4,5,2,3};
const int directions=4;
const int dx[directions]={0,0,-1,1};
const int dy[directions]={-1,1,0,0};
const int of[directions]={-1,-2,0,0}; // -1 bottom , -2 top , 0 same
const int ob[directions]={2,0,3,1}; // offset , counter clock wise
int pos[6][6];
int dist[width*width*24];
int from[width*width*24];
int path[width*width*24];
int pathsize;
int startpos, endpos, curpos;
int num[6];
int i,j,k;
int cx,cy,ck,cb,cf;
int nb,nf;
char c,d;
heap h(dist,width*width*24);
for (i=0; i<6; i++)
for (j=0; j<4; j++) {
pos[i][side[i][j]]=j;
}
fscanf(fi," %c %c",&c,&d);
startpos=((c-'a')*width+(d-'1'))*24+(4*4+pos[4][1]);
fscanf(fi," %c %c",&c,&d);
endpos=((c-'a')*width+(d-'1'))*24+0;
for (i=0; i<6; i++)
fscanf(fi,"%d",num+i);
h.update(startpos,num[4]);
while ((curpos=h.extract())!=-1) {
ck=curpos%24;
cb=ck/4;
cf=ck%4;
cy=(curpos/24)%width;
cx=curpos/(24*width);
/*
printf("\n%c%c:%d%d %d",cx+'a',cy+'1',cb,side[cb][cf],dist
[curpos]);
getchar();
*/
for (i=0; i<directions; i++)
if (cx+dx[i]>=0 && cx+dx[i]<width && cy+dy[i]>=0 && cy+dy[i]
<width) {
nb=side[cb][(cf+ob[i])%4];
if (of[i]==-1) {
nf=pos[nb][cb];
}
else if