oj.uz

답안 #539191

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
539191 2022-03-18T14:42:12 Z Soul234 아름다운 순열 (IZhO12_beauty) C++14
100 / 100
 985 ms 164512 KB 
#include<bits/stdc++.h>
using namespace std;

void DBG() { cerr << "]\n"; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << h; if(sizeof...(t)) cerr << ", ";
    DBG(t...);
}
#ifdef LOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif // LOCAL

#define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--)
#define R0F(i,a) ROF(i,0,a)
#define each(e,a) for(auto &e : (a))
#define sz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb push_back
#define tcT template<class T
#define nl "\n"

using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using str = string;
tcT> using V = vector<T>;
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;

void setIO(string NAME = "") {
    cin.tie(0)->sync_with_stdio(0);
    if(sz(NAME)) {
        freopen((NAME + ".inp").c_str(),"r",stdin);
        freopen((NAME + ".out").c_str(),"w",stdout);
    }
}

constexpr bool onbit(int x, int i) { return x>>i&1;}

const int MX = 25;
int cnt[2][MX], N;
ll dp[1<<20][20];

bool ok(int i, int j) {
    F0R(ind,2) if(cnt[ind][i] == cnt[ind][j]) return true;
    return false;
}

void solve() {
    cin>>N;
    F0R(i,N) {
        int val;
        cin>>val;
        cnt[0][i] = __builtin_popcount(val);
        while(val > 0) {
            cnt[1][i] += (val%3 == 1);
            val /= 3;
        }
    }
    F0R(i,N) dp[1<<i][i] = 1;
    F0R(msk, 1<<N) {
        F0R(i,N) if(onbit(msk, i) && dp[msk][i] > 0) {
            F0R(j,N) if(!onbit(msk, j) && ok(i,j)) {
                dp[msk|(1<<j)][j] += dp[msk][i];
            }
        }
    }
    ll ans = 0;
    F0R(i,N) ans += dp[(1<<N)-1][i];
    cout << ans << nl;
}

int main() {
    setIO();

    int t=1;
    //cin>>t;
    while(t-->0) {
        solve();
    }

    return 0;
}

Compilation message

beauty.cpp: In function 'void setIO(std::string)':
beauty.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen((NAME + ".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
beauty.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen((NAME + ".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 488 KB Output is correct
7 Correct 1 ms 488 KB Output is correct
8 Correct 2 ms 456 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 500 KB Output is correct
11 Correct 10 ms 2900 KB Output is correct
12 Correct 8 ms 2772 KB Output is correct
13 Correct 42 ms 10532 KB Output is correct
14 Correct 204 ms 41292 KB Output is correct
15 Correct 156 ms 41304 KB Output is correct
16 Correct 154 ms 41268 KB Output is correct
17 Correct 236 ms 41316 KB Output is correct
18 Correct 163 ms 41292 KB Output is correct
19 Correct 985 ms 164460 KB Output is correct
20 Correct 627 ms 164512 KB Output is correct