fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4.  
  5. #define null 0
  6.  
  7.  
  8. typedef struct {
  9.     int x1;
  10. 	int y1;
  11. 	int x2;
  12. 	int y2;
  13. } twoCell;
  14.  
  15. typedef struct {
  16. 	int x;
  17. 	int y;
  18. } oneCell;
  19.  
  20.  
  21. typedef struct {
  22. 	long groupId;
  23. 	long numVoltage;
  24. } cell;
  25.  
  26.  
  27. int charToInt(char c) {
  28. 	int i;
  29. 	switch (c) {
  30. 		case 'A':
  31. 			i=0;
  32. 			break;
  33. 		case 'B':
  34. 			i=1;
  35. 			break;
  36. 		case 'C':
  37. 			i=2;
  38. 			break;
  39. 		case 'D':
  40. 			i=3;
  41. 			break;
  42. 		case 'E':
  43. 			i=4;
  44. 			break;
  45. 		case 'F':
  46. 			i=5;
  47. 			break;
  48. 		case 'G':
  49. 			i=6;
  50. 			break;
  51. 		case 'H':
  52. 			i=7;
  53. 			break;
  54. 		case 'I':
  55. 			i=8;
  56. 			break;
  57. 		case 'J':
  58. 			i=9;
  59. 			break;
  60. 		case 'K':
  61. 			i=10;
  62. 			break;
  63. 		case 'L':
  64. 			i=11;
  65. 			break;
  66. 		case 'M':
  67. 			i=12;
  68. 			break;
  69. 		case 'N':
  70. 			i=13;
  71. 			break;
  72. 		case '0':
  73. 			i=14;
  74. 			break;
  75. 		case 'P':
  76. 			i=15;
  77. 			break;
  78. 		case 'Q':
  79. 			i=16;
  80. 			break;
  81. 		case 'R':
  82. 			i=17;
  83. 			break;
  84. 		case 'S':
  85. 			i=18;
  86. 			break;
  87. 		case 'T':
  88. 			i=19;
  89. 			break;
  90. 		case 'U':
  91. 			i=20;
  92. 			break;
  93. 		case 'V':
  94. 			i=21;
  95. 			break;
  96. 		case 'W':
  97. 			i=22;
  98. 			break;
  99. 		case 'X':
  100. 			i=23;
  101. 			break;
  102. 		case 'Y':
  103. 			i=24;
  104. 			break;
  105. 		case 'Z':
  106. 			i=25;
  107. 			break;
  108. 		case 'a':
  109. 			i=26;
  110. 			break;
  111. 		case 'b':
  112. 			i=27;
  113. 			break;
  114. 		case 'c':
  115. 			i=28;
  116. 			break;
  117. 		case 'd':
  118. 			i=29;
  119. 			break;
  120. 		case 'e':
  121. 			i=30;
  122. 			break;
  123. 		case 'f':
  124. 			i=31;
  125. 			break;
  126. 		case 'g':
  127. 			i=32;
  128. 			break;
  129. 		case 'h':
  130. 			i=33;
  131. 			break;
  132. 		case 'i':
  133. 			i=34;
  134. 			break;
  135. 		case 'j':
  136. 			i=35;
  137. 			break;
  138. 		case 'k':
  139. 			i=36;
  140. 			break;
  141. 		case 'l':
  142. 			i=37;
  143. 			break;
  144. 		case 'm':
  145. 			i=38;
  146. 			break;
  147. 		case 'n':
  148. 			i=39;
  149. 			break;
  150. 		case 'o':
  151. 			i=40;
  152. 			break;
  153. 		case 'p':
  154. 			i=41;
  155. 			break;
  156. 		case 'q':
  157. 			i=42;
  158. 			break;
  159. 		case 'r':
  160. 			i=43;
  161. 			break;
  162. 		case 's':
  163. 			i=44;
  164. 			break;
  165. 		case 't':
  166. 			i=45;
  167. 			break;
  168. 		case 'u':
  169. 			i=46;
  170. 			break;
  171. 		case 'v':
  172. 			i=47;
  173. 			break;
  174. 		case 'w':
  175. 			i=48;
  176. 			break;
  177. 		case 'x':
  178. 			i=49;
  179. 			break;
  180. 		case 'y':
  181. 			i=50;
  182. 			break;
  183. 		case 'z':
  184. 			i=51;
  185. 			break;
  186. 	}
  187. 	return i;
  188. }
  189.  
  190. int base52(char msbChar, char lsbChar) {
  191. 	int retVal;
  192. 	int msb, lsb;
  193.  
  194. 	msb = charToInt(msbChar);
  195. 	lsb = charToInt(lsbChar);
  196. 	retVal = 52 * msb + lsb;
  197. 	//printf (" base52 %c %c %d\n", msbChar, lsbChar, retVal);
  198. 	return retVal;
  199. }
  200.  
  201.  
  202. twoCell * readTwoCell(char str[]) {
  203. 	twoCell* retVal = (twoCell*)malloc(sizeof(twoCell));
  204. 	int x1, x2, x3, x4; 
  205. 	retVal->x1 = base52(str[0], str[1]); 
  206. 	retVal->y1 = base52(str[2], str[3]); 
  207. 	retVal->x2 = base52(str[4], str[5]); 
  208. 	retVal->y2 = base52(str[6], str[7]); 
  209. 	return retVal;
  210. }
  211.  
  212. oneCell* readOneCell(char str[]) {
  213. 	oneCell* retVal = (oneCell*)malloc(sizeof(oneCell));
  214. 	retVal->x = base52(str[0], str[1]); 
  215. 	retVal->y = base52(str[2], str[3]); 
  216. 	return retVal;
  217. }
  218.  
  219. void print_board(cell ** board, int r, int c, long groups[], long groupIdToGroup[], long numGroupIds, long numGroups) {
  220. 	int i;
  221. 	int j;
  222. 	long currNumVoltage;
  223. 	long currGroupId;
  224. 	long currGroup;
  225. 	long currGroupVoltage;
  226. 	printf("Printing Board \n");
  227. 	printf("numGroupIds %ld numGroups %ld \n", numGroupIds, numGroups);
  228. 	printf("Printing Board On/Off\n");
  229. 	for(i=0;i<r;i++) {
  230. 		for(j=0;j<c;j++) {
  231. 			currNumVoltage = board[i][j].numVoltage;
  232. 			if (currNumVoltage > 0)
  233. 				printf("1");
  234. 			else {
  235. 				currGroupId = board[i][j].groupId;
  236. 				if (currGroupId != -1) {
  237. 					currGroup = groupIdToGroup[currGroupId];
  238. 					currGroupVoltage = groups[currGroup];
  239. 					if (currGroupVoltage > 0) 
  240. 						printf("1");
  241. 					else
  242. 						printf("0");						
  243. 				}
  244. 				else 
  245. 					printf("0");
  246. 			}		
  247. 		}
  248. 		printf("\n");
  249. 	}
  250. 	printf("Printing Board GroupIds\n");
  251. 	for(i=0;i<r;i++) {
  252. 		for(j=0;j<c;j++) {
  253. 			currGroupId = board[i][j].groupId;
  254. 			printf("%ld", currGroupId);
  255. 		}	
  256. 		printf("\n");	
  257. 	}
  258. 	printf("\n");
  259. 	printf("Printing GroupIds to Groups\n");
  260. 	for(i=0;i<numGroupIds;i++) {
  261. 		currGroup = groupIdToGroup[i];
  262. 		printf("%ld ", currGroup);
  263. 	}
  264. 	printf("\n");
  265. 	printf("Printing Group Voltages \n");
  266. 	for(i=0;i<numGroups;i++) {
  267. 		currNumVoltage = groups[i];
  268. 		printf("%ld ", currNumVoltage);
  269. 	}
  270. 	printf("\n");
  271. }
  272.  
  273. void handleW(cell ** board, int r, int c, int x1, int y1, int x2, int y2, long groups[], long &numGroups, long &numGroupId, long groupIdToGroup[]) {
  274. 	long groupVoltage1, groupVoltage2;
  275. 	long groupId1, groupId2, newGroupId;
  276. 	long group1, group2, newGroup;
  277. 	long totalGroupVoltage;
  278. 	long numVoltage, numVoltage1, numVoltage2;
  279. 	if ( (x1 == x2) && (y1 == y2))
  280. 		return;
  281. 	groupId1 = board[x1][y1].groupId;
  282. 	groupId2 = board[x2][y2].groupId;
  283. 	if(groupId1 == -1) {
  284. 		group1 = -1;
  285. 	}
  286. 	else {
  287. 		group1 = groupIdToGroup[groupId1];
  288. 	}
  289. 	if(groupId2 == -1) {
  290. 		group2 = -1;
  291. 	}
  292. 	else {
  293. 		group2 = groupIdToGroup[groupId2];
  294. 	}
  295. 	if (group1 != -1 && group2 != -1) {
  296. 		if(group1 != group2) {
  297. 			/* Find the smaller group */
  298. 			if (group1 < group2) {
  299. 				/* point the group ids for cell 2 to the smaller group */
  300. 				groupIdToGroup[groupId2]=group1;
  301. 				/* The voltage for smaller group is the sum of voltages for two groups */
  302. 				numVoltage1 = groups[group1];
  303. 				numVoltage2 = groups[group2];
  304. 				totalGroupVoltage = numVoltage1 + numVoltage2;
  305. 				groups[group1]=totalGroupVoltage;
  306. 			}
  307. 			else {
  308. 				/* point the group ids for cell 1 to the smaller group */
  309. 				groupIdToGroup[groupId1]=group2;
  310. 				/* The voltage for smaller group is the sum of voltages for two groups */
  311. 				numVoltage1 = groups[group1];
  312. 				numVoltage2 = groups[group2];
  313. 		 		totalGroupVoltage = numVoltage1 + numVoltage2;
  314. 				groups[group2]=totalGroupVoltage;
  315. 			}
  316. 		}
  317. 	}
  318. 	else {
  319. 		if (!((group1 == -1) && (group2 == -1))) {
  320. 			if (group1 == -1) {
  321. 				/* set groupId of node 1 to group 2 */
  322. 				board[x1][y1].groupId = groupId2;
  323. 				/*if cell 1 has voltage connected to it increment the voltage for group 2 */
  324. 				numVoltage = board[x1][y1].numVoltage;
  325. 				if (numVoltage > 0) {
  326. 					numVoltage2 = groups[group2];
  327. 					totalGroupVoltage = numVoltage + numVoltage2;
  328. 					groups[group2] = totalGroupVoltage;
  329. 				}
  330. 			}
  331. 			else {
  332. 				/* set groupId of node2 to group1 */
  333. 				board[x2][y2].groupId = groupId1;
  334. 				/*if cell 2 has voltage connected to it increment the voltage for group 1 */
  335. 				numVoltage = board[x2][y2].numVoltage;
  336. 				if (numVoltage > 0) {
  337. 					numVoltage1 = groups[group1];
  338. 					totalGroupVoltage = numVoltage + numVoltage1;
  339. 					groups[group1] = totalGroupVoltage;
  340. 				}
  341. 			}
  342. 		}
  343. 		else {
  344. 			/* If both are not in a group create a groupId and a group */
  345. 			newGroupId = numGroupId;
  346. 			numGroupId++;
  347. 			newGroup = numGroups;
  348. 			numGroups++;
  349.  
  350. 			/* set new group id to new group */
  351. 			groupIdToGroup[newGroupId] = newGroup;
  352.  
  353. 			/* The voltage of this group is the sum of numVoltages for two cell */
  354. 			numVoltage1 = board[x1][y1].numVoltage;
  355. 			numVoltage2 = board[x2][y2].numVoltage;
  356. 			totalGroupVoltage = numVoltage1 + numVoltage2;
  357. 			groups[newGroup] = totalGroupVoltage;
  358. 			/* set group id for each cell to this new group id*/
  359. 			board[x1][y1].groupId = newGroupId;
  360. 			board[x2][y2].groupId = newGroupId;
  361. 		}
  362. 	}
  363. 	return;
  364. }
  365. void handleV(cell **board, int r, int c, int x, int y, long groups[], long groupIdToGroup[]) {
  366. 	long currNumVoltage, currGroupVoltage;
  367. 	long currGroupId, currGroup;
  368. 	/* increment num voltage for this cell*/
  369. 	currNumVoltage = board[x][y].numVoltage;
  370. 	board[x][y].numVoltage = currNumVoltage + 1;
  371. 	//printf("handleV o/o board[%d][%d] numVoltage %ld \n", x, y, currNumVoltage + 1);
  372. 	/* if the cell belongs to any group increment the voltage for that group */
  373. 	currGroupId = board[x][y].groupId;
  374. 	if (currGroupId != -1) {
  375. 		currGroup = groupIdToGroup[currGroupId];
  376. 		currGroupVoltage = groups[currGroup];
  377. 		groups[currGroup] = currGroupVoltage + 1;
  378. 	}
  379. 	return;
  380. }
  381. void handleR(cell **board, int r, int c, int x, int y, long groups[], long groupIdToGroup[]) {
  382. 	long currNumVoltage, currGroupVoltage;
  383. 	long currGroupId, currGroup;
  384. 	/* decrement num voltage for this cell*/
  385. 	currNumVoltage = board[x][y].numVoltage;
  386. 	board[x][y].numVoltage = currNumVoltage - 1;
  387. 	/* if the cell belongs to any group decrement the voltage for that group */
  388. 	currGroupId = board[x][y].groupId;
  389. 	if (currGroupId != -1) {
  390. 		currGroup = groupIdToGroup[currGroupId];
  391. 		currGroupVoltage = groups[currGroup];
  392. 		groups[currGroup] = currGroupVoltage - 1;
  393. 	}
  394. 	return;
  395. }
  396. void handleL(cell **board, int r, int c, int x1, int y1, int x2, int y2, long groups[], long groupIdToGroup[]) {
  397. 	int cellVoltage1 = 0;
  398. 	int cellVoltage2 = 0;
  399. 	long numVoltage1, numVoltage2;
  400. 	long group1, group2, groupId1, groupId2;
  401. 	long groupVoltage1, groupVoltage2;
  402. 	/* If the numVoltage of a cell is greater than 1 it is high */
  403. 	numVoltage1 = board[x1][y1].numVoltage;
  404. 	if(numVoltage1 > 0) { 
  405. 		cellVoltage1 = 1;
  406. 	}
  407. 	else {
  408. 		/* If group voltage is greater than 1 it is high */
  409. 		groupId1 = board[x1][y1].groupId;
  410. 		if (groupId1 != -1) {
  411. 			group1 = groupIdToGroup[groupId1]; 
  412. 			groupVoltage1 = groups[group1];
  413. 			if (groupVoltage1 > 0) {
  414. 				cellVoltage1 = 1;			
  415. 			}
  416. 		}
  417. 	}
  418. 	numVoltage2 = board[x2][y2].numVoltage;
  419.  
  420. 	if(numVoltage2 > 0) { 
  421. 		cellVoltage2 = 1;
  422. 	}
  423. 	else {
  424. 		/* If group voltage is greater than 1 it is high */
  425. 		groupId2 = board[x2][y2].groupId;
  426. 		if (groupId2 != -1) {
  427. 			group2 = groupIdToGroup[groupId2];
  428. 			groupVoltage2 = groups[group2];
  429. 			if (groupVoltage2 > 0) {
  430. 				cellVoltage2 = 1;			
  431. 			}
  432. 		}
  433. 	}
  434. 	if (cellVoltage1 != cellVoltage2) {
  435. 		printf("ON\n");
  436. 	}
  437. 	else {
  438. 		printf("OFF\n");
  439. 	}
  440. 	return;
  441. }
  442.  
  443. int main() {
  444. 	char str[9];
  445. 	long n,x; 
  446. 	int r, c;
  447. 	int i,j;
  448. 	char op, ch;
  449. 	oneCell * oc;
  450. 	twoCell * tc;
  451. 	cell **board;
  452. 	scanf("%ld %d %d ", &n, &r, &c);
  453. 	board = (cell**)malloc(sizeof(cell*)*r);
  454. 	for(i=0;i<r;i++) {
  455. 		board[i]=(cell*)malloc(sizeof(cell)*c);
  456. 	}
  457. 	long groups[1000000];
  458. 	long groupIdToGroup[1000000];
  459. 	long numGroups = 0;
  460. 	long numGroupIds = 0;
  461. 	for(i=0;i<r;i++) {
  462. 		for(j=0;j<c;j++) {
  463. 			board[i][j].groupId = -1;
  464. 			board[i][j].numVoltage = 0;
  465. 		}
  466. 	}
  467.  
  468. 	for(x=0;x<n;x++) {
  469. 		scanf("%c", &op);
  470. 		switch (op) {
  471.                         case 'W':
  472.                         {
  473.                                 for(i=0;i<8;i++) {
  474.                                         scanf("%c", &ch);
  475.                                         str[i]=ch;
  476.                                 }
  477.                                 str[i]='\0';
  478.                                 scanf("%c", &ch);
  479.                                 while (ch != '\n')
  480.                                         scanf("%c", &ch);
  481.                                 break;
  482.                         }
  483. 			case 'V': {
  484. 				for(i=0;i<4;i++) {
  485.                                         scanf("%c", &ch);
  486.                                         str[i]=ch;
  487.                                 }
  488.                                 str[i]='\0';
  489.                                 scanf("%c", &ch);
  490.                                 while (ch != '\n')
  491.                                         scanf("%c", &ch);
  492.                                 break;
  493. 			}
  494. 			case 'R': {
  495. 				for(i=0;i<4;i++) {
  496.                                         scanf("%c", &ch);
  497.                                         str[i]=ch;
  498.                                 }
  499.                                 str[i]='\0';
  500.                                 scanf("%c", &ch);
  501.                                 while (ch != '\n')
  502.                                         scanf("%c", &ch);
  503.                                 break;
  504. 			}
  505. 			case 'L':
  506.                         {
  507.                                 for(i=0;i<8;i++) {
  508.                                         scanf("%c", &ch);
  509.                                         str[i]=ch;
  510.                                 }
  511.                                 str[i]='\0';
  512.                                 scanf("%c", &ch);
  513.                                 while (ch != '\n')
  514.                                         scanf("%c", &ch);
  515.                                 break;
  516.                         }
  517.                 }
  518.  
  519.                 switch(op) {
  520. 			case 'W': {
  521. 				tc = readTwoCell(str);
  522. 				//printf("W %d %d %d %d \n", tc->x1, tc->y1, tc->x2, tc->y2);
  523. 				handleW(board, r, c, (tc->y1-1)/5, tc->x1-1, (tc->y2-1)/5, tc->x2-1, groups, numGroups, numGroupIds, groupIdToGroup);
  524. 				free(tc);
  525. 				//print_board(board, r, c, groups, groupIdToGroup, numGroupIds, numGroups);
  526. 				break;
  527. 			}
  528. 			case 'V': {
  529. 				oc = readOneCell(str);	
  530. 				//printf("V %d %d \n", oc->x, oc->y);
  531. 				handleV(board, r, c, (oc->y-1)/5, oc->x-1, groups, groupIdToGroup);
  532. 				free(oc);
  533. 				//print_board(board, r, c, groups, groupIdToGroup, numGroupIds, numGroups);
  534. 				break;
  535. 			}
  536. 			case 'R': {
  537. 				oc = readOneCell(str);		
  538. 				//printf("R %d %d \n", oc->x, oc->y);
  539. 				handleR(board, r, c, (oc->y-1)/5, oc->x-1, groups, groupIdToGroup);
  540. 				//print_board(board, r,c, groups, groupIdToGroup, numGroupIds, numGroups);
  541. 				free(oc);
  542. 				break;
  543. 			}
  544. 			case 'L': {
  545. 				tc = readTwoCell(str);
  546. 				//printf("L %d %d %d %d \n", tc->x1, tc->y1, tc->x2, tc->y2);
  547. 				handleL(board, r, c,(tc->y1-1)/5, tc->x1-1, (tc->y2-1)/5, tc->x2-1, groups, groupIdToGroup);
  548. 				free(tc);
  549. 				break;
  550. 			}
  551. 			default : {
  552. 				break;
  553. 			}
  554. 		}
  555. 	}
  556. 	return 0;
  557. }
Time limit exceeded #stdin #stdout 5s 10552KB
comments (?)
stdin
copy 
2 2 2
VABAE
LABAFACAF
stdout
copy 
Standard output is empty
https://ideone.com/I799ER
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!