oj.uz

Submission #491369

# Submission time Handle Problem Language Result Execution time Memory
491369 2021-12-01T17:41:43 Z acm Beautiful row (IZhO12_beauty) C++14
0 / 100
 182 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 = 1; i < (1 << n); i++) {
    for (int j = 0; j < n; j++) {
      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 1 ms 384 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 7 ms 5964 KB Output is correct
12 Correct 7 ms 5964 KB Output is correct
13 Correct 30 ms 22860 KB Output is correct
14 Correct 150 ms 90516 KB Output is correct
15 Correct 147 ms 90568 KB Output is correct
16 Correct 156 ms 90600 KB Output is correct
17 Correct 166 ms 90564 KB Output is correct
18 Correct 168 ms 90564 KB Output is correct
19 Runtime error 182 ms 262148 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -