Submission #26115

# Submission time Handle Problem Language Result Execution time Memory
26115 2017-06-28T04:53:24 Z imsifile None (JOI16_memory2) C
100 / 100
0 ms 1172 KB
#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;
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 1172 KB Output is correct
2 Correct 0 ms 1172 KB Output is correct
3 Correct 0 ms 1172 KB Output is correct
4 Correct 0 ms 1172 KB Output is correct
5 Correct 0 ms 1172 KB Output is correct
6 Correct 0 ms 1172 KB Output is correct
7 Correct 0 ms 1172 KB Output is correct
8 Correct 0 ms 1172 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 1172 KB Output is correct
2 Correct 0 ms 1172 KB Output is correct
3 Correct 0 ms 1172 KB Output is correct
4 Correct 0 ms 1172 KB Output is correct
5 Correct 0 ms 1172 KB Output is correct
6 Correct 0 ms 1172 KB Output is correct
7 Correct 0 ms 1172 KB Output is correct
8 Correct 0 ms 1172 KB Output is correct
9 Correct 0 ms 1172 KB Output is correct
10 Correct 0 ms 1172 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 1172 KB Output is correct
2 Correct 0 ms 1172 KB Output is correct
3 Correct 0 ms 1172 KB Output is correct
4 Correct 0 ms 1172 KB Output is correct
5 Correct 0 ms 1172 KB Output is correct
6 Correct 0 ms 1172 KB Output is correct
7 Correct 0 ms 1172 KB Output is correct
8 Correct 0 ms 1172 KB Output is correct
9 Correct 0 ms 1172 KB Output is correct
10 Correct 0 ms 1172 KB Output is correct