oj.uz

답안 #167026

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
167026 2019-12-05T10:03:57 Z Hideo 아름다운 순열 (IZhO12_beauty) C++14
0 / 100
 14 ms 1656 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;

int 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);
        for (int j = 0; j < 31; j++){
            if (a & (1 << j))
                bin[i]++;
        }
        int t = a;
        while (t){
            if (t % 3 == 1)
                ter[i]++;
            t /= 3;
        }
    }
    for (int mask = 1; mask < (1 << n); mask++){
        for (int bit = 0; bit < n; bit++){
            if (mask & (1 << bit) && 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];
                }
            }
            else if (mask & (1 << bit))
                dp[mask][bit]++;
        }
    }
    int 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
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 404 KB Output is correct
11 Incorrect 14 ms 1656 KB Output isn't correct
12 Halted 0 ms 0 KB -