Submission #2844149


Source Code Expand

Copy
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N = 40;

int n;
char s[N], t[N];
LL ans;
int dp[20][20];

inline int work(int st) {
  char s1[N], s0[N];
  int t1 = 0, t0 = 0;
  for (int i = 0; i < n; i ++) {
    if ((st >> i) & 1) s1[t1 ++] = s[i];
    else s0[t0 ++] = s[i];
  }
  memset(dp, 0, sizeof dp);
  dp[0][0] = 1;
  for (int i = 0; i <= t1; i ++)
    for (int j = 0; j <= t0; j ++) {
      if (t[i + j] == s1[i]) dp[i + 1][j] += dp[i][j];
      if (t[i + j] == s0[j]) dp[i][j + 1] += dp[i][j];
    }
  return dp[t1][t0];
}

int main() {
  scanf("%d", &n);
  scanf("%s", s);
  memcpy(t, s, sizeof t);
  reverse(t, t + n + n);
  for (int i = 0; i < (1 << n); i ++) ans += work(i);
  printf("%lld\n", ans);
  return 0;
}

Submission Info

Submission Time
Task C - String Coloring
User The_Unbeatable
Language C++14 (GCC 5.4.1)
Score 600
Code Size 852 Byte
Status
Exec Time 145 ms
Memory 256 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:33:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
                  ^
./Main.cpp:34:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s);
                 ^

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 example_0, example_1, example_2, example_3
All 600 / 600 almost_z_0, almost_z_1, almost_z_2, almost_z_3, bigrand_0, bigrand_1, bigrand_2, example_0, example_1, example_2, example_3, handmade_0, handmade_1, nonzero_0, nonzero_1, nonzero_2, nonzero_3, nonzero_4, nonzero_5, nonzero_sc_0, nonzero_sc_1, nonzero_sc_10, nonzero_sc_11, nonzero_sc_2, nonzero_sc_3, nonzero_sc_4, nonzero_sc_5, nonzero_sc_6, nonzero_sc_7, nonzero_sc_8, nonzero_sc_9, nonzero_small_0, nonzero_small_1, nonzero_small_2, nonzero_small_3, rand_0, rand_1, rand_2, runnur_0, runnur_1, runnur_2, runnur_3, runnur_4
Case Name Status Exec Time Memory
almost_z_0 87 ms 256 KB
almost_z_1 90 ms 256 KB
almost_z_2 87 ms 256 KB
almost_z_3 87 ms 256 KB
bigrand_0 73 ms 256 KB
bigrand_1 66 ms 256 KB
bigrand_2 80 ms 256 KB
example_0 1 ms 256 KB
example_1 2 ms 256 KB
example_2 1 ms 256 KB
example_3 86 ms 256 KB
handmade_0 1 ms 256 KB
handmade_1 1 ms 256 KB
nonzero_0 104 ms 256 KB
nonzero_1 100 ms 256 KB
nonzero_2 101 ms 256 KB
nonzero_3 97 ms 256 KB
nonzero_4 95 ms 256 KB
nonzero_5 97 ms 256 KB
nonzero_sc_0 86 ms 256 KB
nonzero_sc_1 145 ms 256 KB
nonzero_sc_10 125 ms 256 KB
nonzero_sc_11 120 ms 256 KB
nonzero_sc_2 111 ms 256 KB
nonzero_sc_3 120 ms 256 KB
nonzero_sc_4 118 ms 256 KB
nonzero_sc_5 119 ms 256 KB
nonzero_sc_6 87 ms 256 KB
nonzero_sc_7 115 ms 256 KB
nonzero_sc_8 129 ms 256 KB
nonzero_sc_9 127 ms 256 KB
nonzero_small_0 2 ms 256 KB
nonzero_small_1 1 ms 256 KB
nonzero_small_2 1 ms 256 KB
nonzero_small_3 13 ms 256 KB
rand_0 1 ms 256 KB
rand_1 1 ms 256 KB
rand_2 1 ms 256 KB
runnur_0 87 ms 256 KB
runnur_1 87 ms 256 KB
runnur_2 96 ms 256 KB
runnur_3 90 ms 256 KB
runnur_4 86 ms 256 KB