oj.uz

Submission #491367

# Submission time Handle Problem Language Result Execution time Memory
491367 2021-12-01T17:38:50 Z acm Beautiful row (IZhO12_beauty) C++14
0 / 100
 196 ms 262148 KB 
#ifdef ONLINE_JUDGE
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#endif
#include <bits/stdc++.h>
#define speed                   \
  ios_base::sync_with_stdio(0); \
  cin.tie(0);                   \
  cout.tie(0);
#define precision     \
  cout.precision(30); \
  cerr.precision(10);
#define ll long long
#define ld long double
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define mp(x, y) make_pair(x, y)
#define all(x) x.begin(), x.end()
#define pc(x) __builtin_popcount(x)
#define pcll(x) __builtin_popcountll(x)
#define F first
#define S second
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
void ioi(string name) {
  freopen((name + ".in").c_str(), "r", stdin);
  freopen((name + ".out").c_str(), "w", stdout);
}
ll n, a[25], b[25], dp[1 << 22][22], c[1 << 22][22];
int main() {
  speed;
  precision;
  // code
  cin >> n;
  for (int i = 0; i < n; i++) {
    ll x;
    cin >> x;
    a[i] = pc(x);
    while (x > 0) {
      b[i] += ((x % 3) == 1);
      x /= 3;
    }
  }
  for (int i = 0; i < n; i++) dp[1 << i][i] = 1;
  for (int i = 0; i < (1 << n); i++) {
    for (int j = 0; j < n; j++) {
      if (i) c[i][j] = (a[__lg(i & -i)] == a[j] || b[__lg(i & -i)] == b[j]);
    }
  }
  for (int i = 0; i < (1 << n); i++) {
    for (int j = 0; j < n; j++) {
      if (i & (1 << j)) continue;
      for (int k = i; k; k ^= (k & -k)) {
        dp[i | (1 << j)][j] += dp[i][__lg(k & -k)] * c[k][j];
      }
    }
  }
  cout << accumulate(dp[(1 << n) - 1], dp[(1 << n) - 1] + n, 0LL);
// endl
#ifndef ONLINE_JUDGE
  cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}

Compilation message

beauty.cpp: In function 'void ioi(std::string)':
beauty.cpp:26:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |   freopen((name + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
beauty.cpp:27:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |   freopen((name + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 236 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 7 ms 5964 KB Output is correct
12 Correct 7 ms 5964 KB Output is correct
13 Correct 35 ms 22864 KB Output is correct
14 Correct 158 ms 90496 KB Output is correct
15 Correct 157 ms 90592 KB Output is correct
16 Correct 184 ms 90532 KB Output is correct
17 Correct 153 ms 90564 KB Output is correct
18 Correct 157 ms 90600 KB Output is correct
19 Runtime error 196 ms 262148 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -