oj.uz

Submission #68377

# Submission time Handle Problem Language Result Execution time Memory
68377 2018-08-17T01:35:45 Z IvanC Snake Escaping (JOI18_snake_escaping) C++11
12 / 100
 526 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 632 KB Output is correct
2 Correct 3 ms 740 KB Output is correct
3 Correct 4 ms 792 KB Output is correct
4 Correct 4 ms 848 KB Output is correct
5 Correct 4 ms 848 KB Output is correct
6 Correct 3 ms 848 KB Output is correct
7 Correct 3 ms 848 KB Output is correct
8 Correct 4 ms 908 KB Output is correct
9 Correct 5 ms 1048 KB Output is correct
10 Correct 4 ms 1048 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 3 ms 740 KB Output is correct
3 Correct 4 ms 792 KB Output is correct
4 Correct 4 ms 848 KB Output is correct
5 Correct 4 ms 848 KB Output is correct
6 Correct 3 ms 848 KB Output is correct
7 Correct 3 ms 848 KB Output is correct
8 Correct 4 ms 908 KB Output is correct
9 Correct 5 ms 1048 KB Output is correct
10 Correct 4 ms 1048 KB Output is correct
11 Correct 276 ms 10480 KB Output is correct
12 Correct 328 ms 10480 KB Output is correct
13 Correct 299 ms 10480 KB Output is correct
14 Correct 275 ms 10480 KB Output is correct
15 Correct 284 ms 10628 KB Output is correct
16 Correct 338 ms 10628 KB Output is correct
17 Correct 310 ms 11012 KB Output is correct
18 Correct 321 ms 12648 KB Output is correct
19 Correct 228 ms 12648 KB Output is correct
20 Correct 280 ms 12648 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 3 ms 740 KB Output is correct
3 Correct 4 ms 792 KB Output is correct
4 Correct 4 ms 848 KB Output is correct
5 Correct 4 ms 848 KB Output is correct
6 Correct 3 ms 848 KB Output is correct
7 Correct 3 ms 848 KB Output is correct
8 Correct 4 ms 908 KB Output is correct
9 Correct 5 ms 1048 KB Output is correct
10 Correct 4 ms 1048 KB Output is correct
11 Correct 276 ms 10480 KB Output is correct
12 Correct 328 ms 10480 KB Output is correct
13 Correct 299 ms 10480 KB Output is correct
14 Correct 275 ms 10480 KB Output is correct
15 Correct 284 ms 10628 KB Output is correct
16 Correct 338 ms 10628 KB Output is correct
17 Correct 310 ms 11012 KB Output is correct
18 Correct 321 ms 12648 KB Output is correct
19 Correct 228 ms 12648 KB Output is correct
20 Correct 280 ms 12648 KB Output is correct
21 Correct 483 ms 17896 KB Output is correct
22 Correct 444 ms 31720 KB Output is correct
23 Correct 513 ms 44440 KB Output is correct
24 Correct 409 ms 58204 KB Output is correct
25 Runtime error 526 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.
26 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 3 ms 740 KB Output is correct
3 Correct 4 ms 792 KB Output is correct
4 Correct 4 ms 848 KB Output is correct
5 Correct 4 ms 848 KB Output is correct
6 Correct 3 ms 848 KB Output is correct
7 Correct 3 ms 848 KB Output is correct
8 Correct 4 ms 908 KB Output is correct
9 Correct 5 ms 1048 KB Output is correct
10 Correct 4 ms 1048 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 632 KB Output is correct
2 Correct 3 ms 740 KB Output is correct
3 Correct 4 ms 792 KB Output is correct
4 Correct 4 ms 848 KB Output is correct
5 Correct 4 ms 848 KB Output is correct
6 Correct 3 ms 848 KB Output is correct
7 Correct 3 ms 848 KB Output is correct
8 Correct 4 ms 908 KB Output is correct
9 Correct 5 ms 1048 KB Output is correct
10 Correct 4 ms 1048 KB Output is correct
11 Correct 276 ms 10480 KB Output is correct
12 Correct 328 ms 10480 KB Output is correct
13 Correct 299 ms 10480 KB Output is correct
14 Correct 275 ms 10480 KB Output is correct
15 Correct 284 ms 10628 KB Output is correct
16 Correct 338 ms 10628 KB Output is correct
17 Correct 310 ms 11012 KB Output is correct
18 Correct 321 ms 12648 KB Output is correct
19 Correct 228 ms 12648 KB Output is correct
20 Correct 280 ms 12648 KB Output is correct
21 Correct 483 ms 17896 KB Output is correct
22 Correct 444 ms 31720 KB Output is correct
23 Correct 513 ms 44440 KB Output is correct
24 Correct 409 ms 58204 KB Output is correct
25 Runtime error 526 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.
26 Halted 0 ms 0 KB -