답안 #970533

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
970533	2024-04-26T16:39:38 Z	mychecksedad	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	315 ms	65536 KB

snake_escaping

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 2e6+100, M = 1e5+10, K = 13, MX = 30;

int n, q, dp[N], p[15];
short int val[N][K];
string s;
void solve(){
  cin >> n >> q >> s;
  if(n > 13) return;
  for(int i = 0; i < N; ++i) dp[i] = 0;
  for(int i = 0; i < (1<<n); ++i){
    int val = 0;
    for(int j =0 ; j < n; ++j){
      if((1<<j)&i) val += 2*p[j];
      else val += p[j];
    }
    dp[val] += s[i] - '0';
  }

  // for(int i = 0; i < p[n]; ++i){
  //   cout << i << ": "; for(int j = 0; j < 5; ++j) cout << val[i][j];
  //   en;
  // }

  for(int i = 0; i < n; ++i){
    for(int mask = 0; mask < p[n]; ++mask){
      if(val[mask][i] == 0){
        dp[mask] += dp[mask + p[i]];
        dp[mask] += dp[mask + 2*p[i]];
      }
    }
  }

  for(int i = 0; i < q; ++i){
    string t; cin >> t;
    int val = 0;
    for(int j = 0; j < n; ++j){
      if(t[n - j - 1] == '0') val += p[j];
      else if(t[n - j - 1] == '1') val += p[j] * 2;
    }
    cout << dp[val] << '\n';
  }
}



int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  p[0] = 1;
  for(int i = 1; i <15; ++i) p[i] = p[i - 1] * 3;
  for(int i = 0; i < N; ++i){
    int x = i;
    for(int j = 0; j < K; ++j){
      val[i][j] = x % 3;
      x /= 3;
    }
  }
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  // cin >> tt;
  while(tt--){
    solve();
    // en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:57:15: warning: unused variable 'aa' [-Wunused-variable]
   57 |   int tt = 1, aa;
      |               ^~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	58964 KB	Output is correct
2	Correct	30 ms	58972 KB	Output is correct
3	Correct	30 ms	59012 KB	Output is correct
4	Correct	33 ms	59304 KB	Output is correct
5	Correct	30 ms	58972 KB	Output is correct
6	Correct	30 ms	58960 KB	Output is correct
7	Correct	30 ms	58972 KB	Output is correct
8	Correct	29 ms	58968 KB	Output is correct
9	Correct	29 ms	59004 KB	Output is correct
10	Correct	30 ms	58964 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	58964 KB	Output is correct
2	Correct	30 ms	58972 KB	Output is correct
3	Correct	30 ms	59012 KB	Output is correct
4	Correct	33 ms	59304 KB	Output is correct
5	Correct	30 ms	58972 KB	Output is correct
6	Correct	30 ms	58960 KB	Output is correct
7	Correct	30 ms	58972 KB	Output is correct
8	Correct	29 ms	58968 KB	Output is correct
9	Correct	29 ms	59004 KB	Output is correct
10	Correct	30 ms	58964 KB	Output is correct
11	Correct	198 ms	65536 KB	Output is correct
12	Correct	203 ms	65536 KB	Output is correct
13	Correct	215 ms	65536 KB	Output is correct
14	Correct	222 ms	65536 KB	Output is correct
15	Correct	206 ms	65536 KB	Output is correct
16	Correct	218 ms	65536 KB	Output is correct
17	Correct	229 ms	65536 KB	Output is correct
18	Correct	165 ms	65536 KB	Output is correct
19	Correct	185 ms	65536 KB	Output is correct
20	Correct	202 ms	65536 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	58964 KB	Output is correct
2	Correct	30 ms	58972 KB	Output is correct
3	Correct	30 ms	59012 KB	Output is correct
4	Correct	33 ms	59304 KB	Output is correct
5	Correct	30 ms	58972 KB	Output is correct
6	Correct	30 ms	58960 KB	Output is correct
7	Correct	30 ms	58972 KB	Output is correct
8	Correct	29 ms	58968 KB	Output is correct
9	Correct	29 ms	59004 KB	Output is correct
10	Correct	30 ms	58964 KB	Output is correct
11	Correct	198 ms	65536 KB	Output is correct
12	Correct	203 ms	65536 KB	Output is correct
13	Correct	215 ms	65536 KB	Output is correct
14	Correct	222 ms	65536 KB	Output is correct
15	Correct	206 ms	65536 KB	Output is correct
16	Correct	218 ms	65536 KB	Output is correct
17	Correct	229 ms	65536 KB	Output is correct
18	Correct	165 ms	65536 KB	Output is correct
19	Correct	185 ms	65536 KB	Output is correct
20	Correct	202 ms	65536 KB	Output is correct
21	Correct	276 ms	65536 KB	Output is correct
22	Correct	271 ms	65536 KB	Output is correct
23	Correct	307 ms	65536 KB	Output is correct
24	Correct	292 ms	65536 KB	Output is correct
25	Correct	275 ms	65536 KB	Output is correct
26	Correct	309 ms	65536 KB	Output is correct
27	Correct	294 ms	65536 KB	Output is correct
28	Correct	215 ms	65536 KB	Output is correct
29	Correct	250 ms	65536 KB	Output is correct
30	Correct	276 ms	65536 KB	Output is correct
31	Correct	284 ms	65536 KB	Output is correct
32	Correct	293 ms	65536 KB	Output is correct
33	Correct	275 ms	65536 KB	Output is correct
34	Correct	286 ms	65536 KB	Output is correct
35	Correct	315 ms	65536 KB	Output is correct
36	Correct	205 ms	65536 KB	Output is correct
37	Correct	265 ms	65536 KB	Output is correct
38	Correct	261 ms	65536 KB	Output is correct
39	Correct	295 ms	65536 KB	Output is correct
40	Correct	283 ms	65536 KB	Output is correct

Subtask #4
0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	58964 KB	Output is correct
2	Correct	30 ms	58972 KB	Output is correct
3	Correct	30 ms	59012 KB	Output is correct
4	Correct	33 ms	59304 KB	Output is correct
5	Correct	30 ms	58972 KB	Output is correct
6	Correct	30 ms	58960 KB	Output is correct
7	Correct	30 ms	58972 KB	Output is correct
8	Correct	29 ms	58968 KB	Output is correct
9	Correct	29 ms	59004 KB	Output is correct
10	Correct	30 ms	58964 KB	Output is correct
11	Incorrect	29 ms	53996 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	58964 KB	Output is correct
2	Correct	30 ms	58972 KB	Output is correct
3	Correct	30 ms	59012 KB	Output is correct
4	Correct	33 ms	59304 KB	Output is correct
5	Correct	30 ms	58972 KB	Output is correct
6	Correct	30 ms	58960 KB	Output is correct
7	Correct	30 ms	58972 KB	Output is correct
8	Correct	29 ms	58968 KB	Output is correct
9	Correct	29 ms	59004 KB	Output is correct
10	Correct	30 ms	58964 KB	Output is correct
11	Correct	198 ms	65536 KB	Output is correct
12	Correct	203 ms	65536 KB	Output is correct
13	Correct	215 ms	65536 KB	Output is correct
14	Correct	222 ms	65536 KB	Output is correct
15	Correct	206 ms	65536 KB	Output is correct
16	Correct	218 ms	65536 KB	Output is correct
17	Correct	229 ms	65536 KB	Output is correct
18	Correct	165 ms	65536 KB	Output is correct
19	Correct	185 ms	65536 KB	Output is correct
20	Correct	202 ms	65536 KB	Output is correct
21	Correct	276 ms	65536 KB	Output is correct
22	Correct	271 ms	65536 KB	Output is correct
23	Correct	307 ms	65536 KB	Output is correct
24	Correct	292 ms	65536 KB	Output is correct
25	Correct	275 ms	65536 KB	Output is correct
26	Correct	309 ms	65536 KB	Output is correct
27	Correct	294 ms	65536 KB	Output is correct
28	Correct	215 ms	65536 KB	Output is correct
29	Correct	250 ms	65536 KB	Output is correct
30	Correct	276 ms	65536 KB	Output is correct
31	Correct	284 ms	65536 KB	Output is correct
32	Correct	293 ms	65536 KB	Output is correct
33	Correct	275 ms	65536 KB	Output is correct
34	Correct	286 ms	65536 KB	Output is correct
35	Correct	315 ms	65536 KB	Output is correct
36	Correct	205 ms	65536 KB	Output is correct
37	Correct	265 ms	65536 KB	Output is correct
38	Correct	261 ms	65536 KB	Output is correct
39	Correct	295 ms	65536 KB	Output is correct
40	Correct	283 ms	65536 KB	Output is correct
41	Incorrect	29 ms	53996 KB	Output isn't correct
42	Halted	0 ms	0 KB	-

답안 #970533

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 10.0 / 10.0

Subtask #4 0 / 53.0

Subtask #5 0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
7.0 / 7.0

Subtask #3
10.0 / 10.0

Subtask #4
0 / 53.0

Subtask #5
0 / 25.0