oj.uz

Submission #167028

# Submission time Handle Problem Language Result Execution time Memory
167028 2019-12-05T10:12:49 Z Hideo Beautiful row (IZhO12_beauty) C++14
100 / 100
 1205 ms 172792 KB 
// Need to git gud and reach 1900+
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
using namespace std;

#define all(s) s.begin(), s.end()
#define ok puts("ok")
#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define vi vector < int >
#define pi pair < int, int >
#define prev prev123
#define next next123
#define pow pow123
#define left left123
#define right right123

const int N = 27;
const int INF = 1e9 + 7;

ll dp[(1 << 20) + 1][21];
int bin[N], ter[N];
int n;

main(){ // If you don't know what to do, check the text box at the bottom
    cin >> n;
    for (int i = 0; i < n; i++){
        int a;
        scanf("%d", &a);
        bin[i] = __builtin_popcount(a);
        while (a){
            if (a % 3 == 1)
                ter[i]++;
            a /= 3;
        }
    }
    for (int i = 0; i < n; i++)
        dp[(1 << i)][i] = 1;

    for (int mask = 1; mask < (1 << n); mask++){
        for (int bit = 0; bit < n; bit++){
            if (mask & (1 << bit)){
                for (int last = 0; last < n; last++){
                    if (last == bit)
                        continue;
                    if (mask & (1 << last) && (ter[bit] == ter[last]
                                            || bin[bit] == bin[last]))
                        dp[mask][bit] += dp[mask ^ (1 << bit)][last];
                }
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i < n; i++)
        ans += dp[(1 << n) - 1][i];
    cout << ans << endl;
}

/*
    Totally not inspired by BenQ's template
    Things you should do:
    1. Look for stupid typos in code e.g 1 instead of -1 etc
    2. Check if there is no infinite loops
    3. "Measure twice, cut once"
    4. Stay focused
*/

Compilation message

beauty.cpp:30:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){ // If you don't know what to do, check the text box at the bottom
      ^
beauty.cpp: In function 'int main()':
beauty.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a);
         ~~~~~^~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 14 ms 3036 KB Output is correct
12 Correct 13 ms 3064 KB Output is correct
13 Correct 57 ms 11128 KB Output is correct
14 Correct 260 ms 43512 KB Output is correct
15 Correct 257 ms 43516 KB Output is correct
16 Correct 258 ms 43384 KB Output is correct
17 Correct 245 ms 43512 KB Output is correct
18 Correct 264 ms 43360 KB Output is correct
19 Correct 1205 ms 172708 KB Output is correct
20 Correct 1171 ms 172792 KB Output is correct