oj.uz

Submission #523467

# Submission time Handle Problem Language Result Execution time Memory
523467 2022-02-07T17:15:43 Z lukameladze Beautiful row (IZhO12_beauty) C++14
100 / 100
 581 ms 172732 KB 
# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define int long long
using namespace std;
const int N = 21;
int fix[N][N],lst,ans,lst1,a[N],n,dp[(1<<N)][N];
int ones(int x) {
    int cnt = 0;
    while (x) {
        cnt += ((x%3)==1);
        x/=3;
    }
    return cnt;
}
main() {
    cin>>n;
    for (int i = 0; i < n; i++) {
        cin>>a[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (__builtin_popcount(a[i]) == __builtin_popcount(a[j])) {
                fix[i][j] = fix[j][i] = 1;
                continue;
            }
            if (ones(a[i]) == ones(a[j])) {
                fix[i][j] = fix[j][i] = 1;
                continue;
            }
        }
    }
    for (int i = 1; i < (1<<n); i++) {
        vector <int> v;
        for (int j = 0; j < n; j++) {
            if ((1<<j)&i) v.pb(j);
        }
        if (__builtin_popcount(i) == 1){ dp[i][v[0]] = 1; continue; }
        for (int j = 0; j < v.size(); j++) { lst = v[j];
            for (int j1 = 0; j1 < v.size(); j1++) { lst1 = v[j1];
                if (j == j1) continue;
                if (fix[lst][lst1]) {
                dp[i][lst] += dp[i ^ (1<<lst)][lst1];
                }
            }
            if (i == (1<<n) - 1) ans += dp[i][lst];//, ans %= mod;
        }
    }
    cout<<ans<<endl;
}

Compilation message

beauty.cpp:17:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   17 | main() {
      | ^~~~
beauty.cpp: In function 'int main()':
beauty.cpp:40:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for (int j = 0; j < v.size(); j++) { lst = v[j];
      |                         ~~^~~~~~~~~~
beauty.cpp:41:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |             for (int j1 = 0; j1 < v.size(); j1++) { lst1 = v[j1];
      |                              ~~~^~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 284 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 428 KB Output is correct
7 Correct 2 ms 424 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 6 ms 2892 KB Output is correct
12 Correct 6 ms 2892 KB Output is correct
13 Correct 29 ms 11036 KB Output is correct
14 Correct 169 ms 43368 KB Output is correct
15 Correct 110 ms 43384 KB Output is correct
16 Correct 137 ms 43420 KB Output is correct
17 Correct 144 ms 43368 KB Output is correct
18 Correct 178 ms 43312 KB Output is correct
19 Correct 581 ms 172728 KB Output is correct
20 Correct 495 ms 172732 KB Output is correct