oj.uz

Submission #321725

# Submission time Handle Problem Language Result Execution time Memory
321725 2020-11-13T06:12:19 Z seedkin Get Hundred Points! (FXCUP4_hundred) C++17
0 / 100
 2 ms 620 KB 
#include "hundred.h"
#include <stdio.h>

#define aBit 1
#define bBit 2
#define cBit 4

#define aIdx 0
#define bIdx 1
#define cIdx 2

int dir[100][8][100];   // dir[idx][char bit][target idx] =  char bit

std::string GetHundredPoints(int A, int B, int C) {
	// int a, b, c;
	// a = b = c = 0;
	int isCorret[105];
	int candi[105];
	// char ans[100];
	int bit[500];
	bit['A'] = aBit;
	bit['B'] = bBit;
	bit['C'] = cBit;
	// char c[5];
	// c[aBit] = 'A';
	// c[bBit] = 'B';
	// c[cBit] = 'C';

	std::string str = std::string(A, 'A') + std::string(B, 'B') + std::string(C, 'C');
	for (int i = 0; i < 100; i++) {
		isCorret[i] = 0;
		// ans[i] = 'A';
		candi[i] = aBit | bBit | cBit;
	}
	for (int i = 0; i < 100; i++) {
		for (int j = 0; j < 8; j++) {
			for (int k = 0; k < 100; k++) {
				dir[i][j][k] = -1;
			}
		}
	}
	int result = Mark(str);
	if (result == A + B + C) return str;
	int prevResult = result;

	for (int i = 0; i < A + B + C; i++) {
		if(result == 98) {
			int find = i;
			int a, b;
			a= b= -1;
			for(int j = i; j < A + B + C; j++) {
				if(isCorret[j]) find++;
				else {
					if( a== -1) a = j;
					else b= j;
				}
			}
			if(find == 98) {				
				char temp = str[a];
				str[a] = str[b];
				str[b] = temp;
				return str;
			}			
		}
		
		if (isCorret[i]) continue;
		if (candi[i] == aBit && str[i] == 'A') {
			isCorret[i] = 1;
			continue;
		}
		if (candi[i] == bBit && str[i] == 'B') {
			isCorret[i] = 1;
			continue;
		}
		if (candi[i] == cBit && str[i] == 'C') {
			isCorret[i] = 1;
			continue;
		}
		for (int j = i + 1; j < A + B + C; j++) {
			if (candi[i] == aBit || candi[i] == bBit || candi[i] == cBit) break;;
			if (candi[j] == aBit && str[j] == 'A') {
				isCorret[j] = 1;				
			}
			if (candi[j] == bBit && str[j] == 'B') {
				isCorret[j] = 1;				
			}
			if (candi[j] == cBit && str[j] == 'C') {
				isCorret[j] = 1;				
			}			
			if (str[i] == str[j]) continue;
			if ((candi[i] & bit[str[j]]) == 0) continue;			
			char temp = str[i];
			str[i] = str[j];
			str[j] = temp;

			result = Mark(str);
			if (result == A + B + C) return str;
			int r = result - prevResult;
			if (r == 0) {
				temp = str[i];
				str[i] = str[j];
				str[j] = temp;
				if(isCorret[j]) {
					candi[i] = bit[str[j]];
					break;
				} else {					
					dir[i][bit['A']][j] = bit['A'];
					dir[i][bit['B']][j] = bit['B'];
					dir[i][bit['C']][j] = bit['C'];
				}				
				continue;
			}
			else if (r == 1) {
				prevResult = result;
				candi[i] &= ~bit[str[j]];
				candi[j] &= ~bit[str[i]];
				dir[i][bit[str[i]]][j] = candi[i] & (~bit[str[i]]);
				dir[i][(candi[i] & (~bit[str[i]]))][j] = bit[str[j]];
				continue;
			}
			else if (r == 2) {
				prevResult = result;
				candi[i] = bit[str[i]];
				candi[j] = bit[str[j]];
				isCorret[i] = 1;
				isCorret[j] = 1;
				for (int k = i + 1; k < j; k++) {
					if (isCorret[k]) continue;
					if (dir[i][bit[str[i]]][k] == -1) continue;
					candi[k] = dir[i][bit[str[i]]][k];
				}
				break;
			}
			else if (r == -1) {
				temp = str[i];
				str[i] = str[j];
				str[j] = temp;
				if(isCorret[j]) {
					candi[i] &= ~bit[str[j]];
					candi[i] &= ~bit[str[i]];
					break;
				} else {
					candi[i] &= ~bit[str[j]];
					candi[j] &= ~bit[str[i]];
					dir[i][bit[str[i]]][j] = candi[i] & (~bit[str[i]]);
					dir[i][(candi[i] & (~bit[str[i]]))][j] = bit[str[j]];
				}				
				continue;
			}
			else {
				temp = str[i];
				str[i] = str[j];
				str[j] = temp;
				candi[i] &= ~bit[str[i]];
				candi[j] &= ~bit[str[j]];
				isCorret[i] = 1;
				isCorret[j] = 1;
				for (int k = i + 1; k < j; k++) {
					if (isCorret[k]) continue;
					if (dir[i][bit[str[i]]][k] == -1) continue;
					candi[k] = dir[i][bit[str[i]]][k];
				}
				break;
			}
		}

		if (isCorret[i]) continue;

		for (int j = i + 1; j < A + B + C; j++) {
			if (!(candi[i] == aBit || candi[i] == bBit || candi[i] == cBit)) break;;
			if (isCorret[j]) continue;
			if (candi[j] == aBit && str[j] == 'A') {
				isCorret[j] = 1;
				continue;
			}
			if (candi[j] == bBit && str[j] == 'B') {
				isCorret[j] = 1;
				continue;
			}
			if (candi[j] == cBit && str[j] == 'C') {
				isCorret[j] = 1;
				continue;
			}
			if (str[i] == str[j]) continue;
			if ((candi[i] & bit[str[j]]) == 0) continue;
			if ((candi[j] & bit[str[i]]) == 0) continue;

			char temp = str[i];
			str[i] = str[j];
			str[j] = temp;

			result = Mark(str);
			if (result == A + B + C) return str;
			int r = result - prevResult;
			if (r == 2) {
				prevResult = result;
				candi[i] = bit[str[i]];
				candi[j] = bit[str[j]];
				isCorret[i] = 1;
				isCorret[j] = 1;
			}
			else if (r == 1) {
				prevResult = result;
				candi[i] = bit[str[i]];
				candi[j] &= ~bit[str[j]];
				candi[j] &= ~bit[str[i]];
				isCorret[i] = 1;
			}
			else if (r == 0) {
				prevResult = result;
				candi[i] = bit[str[i]];
				candi[j] = bit[str[i]];
				isCorret[i] = 1;
			}
			else {
				printf("err %d\n", r);
			}

			for (int k = i + 1; k < j; k++) {
				if (isCorret[k]) continue;
				if (dir[i][bit[str[i]]][k] == -1) continue;
				candi[k] = dir[i][bit[str[i]]][k];
			}
			break;
		}
	}

	return str;
}

Compilation message

hundred.cpp: In function 'std::string GetHundredPoints(int, int, int)':
hundred.cpp:91:30: warning: array subscript has type 'char' [-Wchar-subscripts]
   91 |    if ((candi[i] & bit[str[j]]) == 0) continue;
      |                              ^
hundred.cpp:104:27: warning: array subscript has type 'char' [-Wchar-subscripts]
  104 |      candi[i] = bit[str[j]];
      |                           ^
hundred.cpp:115:28: warning: array subscript has type 'char' [-Wchar-subscripts]
  115 |     candi[i] &= ~bit[str[j]];
      |                            ^
hundred.cpp:116:28: warning: array subscript has type 'char' [-Wchar-subscripts]
  116 |     candi[j] &= ~bit[str[i]];
      |                            ^
hundred.cpp:117:22: warning: array subscript has type 'char' [-Wchar-subscripts]
  117 |     dir[i][bit[str[i]]][j] = candi[i] & (~bit[str[i]]);
      |                      ^
hundred.cpp:117:53: warning: array subscript has type 'char' [-Wchar-subscripts]
  117 |     dir[i][bit[str[i]]][j] = candi[i] & (~bit[str[i]]);
      |                                                     ^
hundred.cpp:118:36: warning: array subscript has type 'char' [-Wchar-subscripts]
  118 |     dir[i][(candi[i] & (~bit[str[i]]))][j] = bit[str[j]];
      |                                    ^
hundred.cpp:118:56: warning: array subscript has type 'char' [-Wchar-subscripts]
  118 |     dir[i][(candi[i] & (~bit[str[i]]))][j] = bit[str[j]];
      |                                                        ^
hundred.cpp:123:26: warning: array subscript has type 'char' [-Wchar-subscripts]
  123 |     candi[i] = bit[str[i]];
      |                          ^
hundred.cpp:124:26: warning: array subscript has type 'char' [-Wchar-subscripts]
  124 |     candi[j] = bit[str[j]];
      |                          ^
hundred.cpp:129:27: warning: array subscript has type 'char' [-Wchar-subscripts]
  129 |      if (dir[i][bit[str[i]]][k] == -1) continue;
      |                           ^
hundred.cpp:130:34: warning: array subscript has type 'char' [-Wchar-subscripts]
  130 |      candi[k] = dir[i][bit[str[i]]][k];
      |                                  ^
hundred.cpp:139:29: warning: array subscript has type 'char' [-Wchar-subscripts]
  139 |      candi[i] &= ~bit[str[j]];
      |                             ^
hundred.cpp:140:29: warning: array subscript has type 'char' [-Wchar-subscripts]
  140 |      candi[i] &= ~bit[str[i]];
      |                             ^
hundred.cpp:143:29: warning: array subscript has type 'char' [-Wchar-subscripts]
  143 |      candi[i] &= ~bit[str[j]];
      |                             ^
hundred.cpp:144:29: warning: array subscript has type 'char' [-Wchar-subscripts]
  144 |      candi[j] &= ~bit[str[i]];
      |                             ^
hundred.cpp:145:23: warning: array subscript has type 'char' [-Wchar-subscripts]
  145 |      dir[i][bit[str[i]]][j] = candi[i] & (~bit[str[i]]);
      |                       ^
hundred.cpp:145:54: warning: array subscript has type 'char' [-Wchar-subscripts]
  145 |      dir[i][bit[str[i]]][j] = candi[i] & (~bit[str[i]]);
      |                                                      ^
hundred.cpp:146:37: warning: array subscript has type 'char' [-Wchar-subscripts]
  146 |      dir[i][(candi[i] & (~bit[str[i]]))][j] = bit[str[j]];
      |                                     ^
hundred.cpp:146:57: warning: array subscript has type 'char' [-Wchar-subscripts]
  146 |      dir[i][(candi[i] & (~bit[str[i]]))][j] = bit[str[j]];
      |                                                         ^
hundred.cpp:154:28: warning: array subscript has type 'char' [-Wchar-subscripts]
  154 |     candi[i] &= ~bit[str[i]];
      |                            ^
hundred.cpp:155:28: warning: array subscript has type 'char' [-Wchar-subscripts]
  155 |     candi[j] &= ~bit[str[j]];
      |                            ^
hundred.cpp:160:27: warning: array subscript has type 'char' [-Wchar-subscripts]
  160 |      if (dir[i][bit[str[i]]][k] == -1) continue;
      |                           ^
hundred.cpp:161:34: warning: array subscript has type 'char' [-Wchar-subscripts]
  161 |      candi[k] = dir[i][bit[str[i]]][k];
      |                                  ^
hundred.cpp:185:30: warning: array subscript has type 'char' [-Wchar-subscripts]
  185 |    if ((candi[i] & bit[str[j]]) == 0) continue;
      |                              ^
hundred.cpp:186:30: warning: array subscript has type 'char' [-Wchar-subscripts]
  186 |    if ((candi[j] & bit[str[i]]) == 0) continue;
      |                              ^
hundred.cpp:197:26: warning: array subscript has type 'char' [-Wchar-subscripts]
  197 |     candi[i] = bit[str[i]];
      |                          ^
hundred.cpp:198:26: warning: array subscript has type 'char' [-Wchar-subscripts]
  198 |     candi[j] = bit[str[j]];
      |                          ^
hundred.cpp:204:26: warning: array subscript has type 'char' [-Wchar-subscripts]
  204 |     candi[i] = bit[str[i]];
      |                          ^
hundred.cpp:205:28: warning: array subscript has type 'char' [-Wchar-subscripts]
  205 |     candi[j] &= ~bit[str[j]];
      |                            ^
hundred.cpp:206:28: warning: array subscript has type 'char' [-Wchar-subscripts]
  206 |     candi[j] &= ~bit[str[i]];
      |                            ^
hundred.cpp:211:26: warning: array subscript has type 'char' [-Wchar-subscripts]
  211 |     candi[i] = bit[str[i]];
      |                          ^
hundred.cpp:212:26: warning: array subscript has type 'char' [-Wchar-subscripts]
  212 |     candi[j] = bit[str[i]];
      |                          ^
hundred.cpp:221:26: warning: array subscript has type 'char' [-Wchar-subscripts]
  221 |     if (dir[i][bit[str[i]]][k] == -1) continue;
      |                          ^
hundred.cpp:222:33: warning: array subscript has type 'char' [-Wchar-subscripts]
  222 |     candi[k] = dir[i][bit[str[i]]][k];
      |                                 ^

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 620 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Runtime error 2 ms 620 KB Execution killed with signal 13 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #2
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 620 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Runtime error 2 ms 620 KB Execution killed with signal 13 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -