oj.uz

Submission #491370

# Submission time Handle Problem Language Result Execution time Memory
491370 2021-12-01T17:43:27 Z acm Beautiful row (IZhO12_beauty) C++14
0 / 100
 204 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 & -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 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 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 8 ms 5964 KB Output is correct
12 Correct 8 ms 5964 KB Output is correct
13 Correct 33 ms 22860 KB Output is correct
14 Correct 162 ms 90564 KB Output is correct
15 Correct 162 ms 90556 KB Output is correct
16 Correct 166 ms 90564 KB Output is correct
17 Correct 180 ms 90628 KB Output is correct
18 Correct 162 ms 90596 KB Output is correct
19 Runtime error 204 ms 262148 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -