Submission #26115

#	Time	Username	Problem	Language	Result	Execution time	Memory
26115		imsifile	Memory 2 (JOI16_memory2)	C11	100 / 100	0 ms	1172 KiB

memory2

#include "Memory2_lib.h"
#include <memory.h>

int hist[111][111];
int grp[200][3], chk[200], gcn, dap[200], bin[101];

int Flip2(int a, int b){
	if(hist[a][b] < 0) return hist[a][b] = hist[b][a] = Flip(a, b);
	return hist[a][b];
}

void Answer2(int a, int b, int d){
	Answer(a, b, d);
	dap[a]=dap[b]=d;
}

void make_node(int a, int b){
	grp[gcn][0]=a, grp[gcn][1]=b, grp[gcn][2]=Flip2(a,b);
	gcn++;
}

int find_dup(){
	memset(bin, 0, sizeof(bin));
	int scn=0;
	for(int i=gcn-1; i>=0; i--){
		if(chk[i]) continue;
		if(bin[grp[i][2]]){
			int j=bin[grp[i][2]]-1;
			chk[i]=chk[j]=1;
			if(Flip2(grp[i][0],grp[j][0]) != grp[i][2]){
				Answer2(grp[i][1], grp[j][1], grp[i][2]);
				make_node(grp[i][0], grp[j][0]);
			}
			else if(Flip2(grp[i][1],grp[j][0]) != grp[i][2]){
				Answer2(grp[i][0], grp[j][1], grp[i][2]);
				make_node(grp[i][1], grp[j][0]);
			}
			else if(Flip2(grp[i][0],grp[j][1]) != grp[i][2]){
				Answer2(grp[i][1], grp[j][0], grp[i][2]);
				make_node(grp[i][0], grp[j][1]);
			}
			else if(Flip2(grp[i][1],grp[j][1]) != grp[i][2]){
				Answer2(grp[i][0], grp[j][0], grp[i][2]);
				make_node(grp[i][1], grp[j][1]);
			}
			return 1;
		}
		else bin[grp[i][2]]=i+1, scn++;
	}
	for(int i=0; i<gcn; i++){
		if(chk[i]) continue;
		Answer(grp[i][0], grp[i][1], grp[i][2]);
		dap[grp[i][0]]=dap[grp[i][1]]=grp[i][2];
		chk[i]=1;
	}
	return scn;
}

void Solve(int T, int N){
	for(int i=0; i<2*N; i++){
		dap[i]=-1; chk[i]=0;
		for(int j=0; j<2*N; j++) hist[i][j] = -1;
	}
	for(int i=0; i<2*N; i+=2) make_node(i, i+1);
	int know=0;
	for(know=0; know<N-1;) know += find_dup();
	if(know == N-1){
		int a=-1, b=-1, d=-1;
		memset(bin, 0, sizeof(bin));
		for(int i=0; i<2*N; i++){
			if(dap[i]<0 && a==-1) a=i;
			else if(dap[i]<0) b=i;
			else bin[dap[i]]=1;
		}
		for(int i=0; i<N; i++){
			if(!bin[i]) d=i;
		}
		Answer2(a, b, d);
	}
	return;
}

• Subtask 1: 10 / 10
• Subtask 2: 50 / 50
• Subtask 3: 40 / 40