oj.uz

Submission #68376

# Submission time Handle Problem Language Result Execution time Memory
68376 2018-08-17T01:32:37 Z IvanC Snake Escaping (JOI18_snake_escaping) C++17
12 / 100
 420 ms 66560 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXL = 15;
const int MAXN = (1 << 13) + 3;
const int MAXV = 1594326; 

char entrada[MAXL];
int pot2[MAXL],pot3[MAXL];
int tab[MAXV],valor[MAXN];
int L,Q;

void brute(int pos,int base3,int base2,int first_2){

	if(pos == L){
		if(first_2 == -1){
			tab[base3] = valor[base2];
		}
		else{
			tab[base3] = tab[base3 - pot3[first_2]] + tab[base3 - 2*pot3[first_2]]; 
		}
		return;
	}

	brute(pos + 1, base3, base2, first_2 );
	brute(pos + 1, base3 + pot3[pos], base2 + pot2[pos], first_2 );
	brute(pos + 1, base3 + 2*pot3[pos], base2, (first_2 != -1) ? (first_2) : (pos) );

}

int main(){

	scanf("%d %d",&L,&Q);
	assert(L <= 13);

	for(int i = 0;i<(1 << L);i++){
		char c;
		scanf(" %c",&c);
		valor[i] = (c - '0');
	}

	pot3[0] = pot2[0] = 1;
	for(int i = 1;i<L;i++){
		pot3[i] = pot3[i-1]*3;
		pot2[i] = pot2[i-1]*2;
	}

	brute(0,0,0,-1);

	for(int q = 0;q<Q;q++){

		int numero = 0;
		scanf("%s",entrada);

		for(int i = 0,j = L - 1;i<L;i++,j--){
			int davez = entrada[i] - '0';
			if(entrada[i] == '?') davez = 2;
			numero += pot3[j]*davez;
		}

		printf("%d\n",tab[numero]);

	}

	return 0;

}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&L,&Q);
  ~~~~~^~~~~~~~~~~~~~~
snake_escaping.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c",&c);
   ~~~~~^~~~~~~~~~
snake_escaping.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",entrada);
   ~~~~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 636 KB Output is correct
2 Correct 5 ms 872 KB Output is correct
3 Correct 4 ms 872 KB Output is correct
4 Correct 3 ms 872 KB Output is correct
5 Correct 4 ms 872 KB Output is correct
6 Correct 3 ms 872 KB Output is correct
7 Correct 4 ms 872 KB Output is correct
8 Correct 4 ms 940 KB Output is correct
9 Correct 4 ms 940 KB Output is correct
10 Correct 4 ms 940 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 636 KB Output is correct
2 Correct 5 ms 872 KB Output is correct
3 Correct 4 ms 872 KB Output is correct
4 Correct 3 ms 872 KB Output is correct
5 Correct 4 ms 872 KB Output is correct
6 Correct 3 ms 872 KB Output is correct
7 Correct 4 ms 872 KB Output is correct
8 Correct 4 ms 940 KB Output is correct
9 Correct 4 ms 940 KB Output is correct
10 Correct 4 ms 940 KB Output is correct
11 Correct 314 ms 7328 KB Output is correct
12 Correct 321 ms 7328 KB Output is correct
13 Correct 263 ms 7328 KB Output is correct
14 Correct 254 ms 7328 KB Output is correct
15 Correct 301 ms 7404 KB Output is correct
16 Correct 308 ms 7404 KB Output is correct
17 Correct 359 ms 17416 KB Output is correct
18 Correct 322 ms 30024 KB Output is correct
19 Correct 235 ms 37896 KB Output is correct
20 Correct 325 ms 50348 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 636 KB Output is correct
2 Correct 5 ms 872 KB Output is correct
3 Correct 4 ms 872 KB Output is correct
4 Correct 3 ms 872 KB Output is correct
5 Correct 4 ms 872 KB Output is correct
6 Correct 3 ms 872 KB Output is correct
7 Correct 4 ms 872 KB Output is correct
8 Correct 4 ms 940 KB Output is correct
9 Correct 4 ms 940 KB Output is correct
10 Correct 4 ms 940 KB Output is correct
11 Correct 314 ms 7328 KB Output is correct
12 Correct 321 ms 7328 KB Output is correct
13 Correct 263 ms 7328 KB Output is correct
14 Correct 254 ms 7328 KB Output is correct
15 Correct 301 ms 7404 KB Output is correct
16 Correct 308 ms 7404 KB Output is correct
17 Correct 359 ms 17416 KB Output is correct
18 Correct 322 ms 30024 KB Output is correct
19 Correct 235 ms 37896 KB Output is correct
20 Correct 325 ms 50348 KB Output is correct
21 Runtime error 420 ms 66560 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
22 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 636 KB Output is correct
2 Correct 5 ms 872 KB Output is correct
3 Correct 4 ms 872 KB Output is correct
4 Correct 3 ms 872 KB Output is correct
5 Correct 4 ms 872 KB Output is correct
6 Correct 3 ms 872 KB Output is correct
7 Correct 4 ms 872 KB Output is correct
8 Correct 4 ms 940 KB Output is correct
9 Correct 4 ms 940 KB Output is correct
10 Correct 4 ms 940 KB Output is correct
11 Runtime error 4 ms 66560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 636 KB Output is correct
2 Correct 5 ms 872 KB Output is correct
3 Correct 4 ms 872 KB Output is correct
4 Correct 3 ms 872 KB Output is correct
5 Correct 4 ms 872 KB Output is correct
6 Correct 3 ms 872 KB Output is correct
7 Correct 4 ms 872 KB Output is correct
8 Correct 4 ms 940 KB Output is correct
9 Correct 4 ms 940 KB Output is correct
10 Correct 4 ms 940 KB Output is correct
11 Correct 314 ms 7328 KB Output is correct
12 Correct 321 ms 7328 KB Output is correct
13 Correct 263 ms 7328 KB Output is correct
14 Correct 254 ms 7328 KB Output is correct
15 Correct 301 ms 7404 KB Output is correct
16 Correct 308 ms 7404 KB Output is correct
17 Correct 359 ms 17416 KB Output is correct
18 Correct 322 ms 30024 KB Output is correct
19 Correct 235 ms 37896 KB Output is correct
20 Correct 325 ms 50348 KB Output is correct
21 Runtime error 420 ms 66560 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
22 Halted 0 ms 0 KB -