oj.uz

Submission #312680

# Submission time Handle Problem Language Result Execution time Memory
312680 2020-10-14T03:53:45 Z Trickster Beautiful row (IZhO12_beauty) C++14
0 / 100
 3000 ms 25212 KB 
#include <algorithm>
#include <string.h>
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
#include <map>

using namespace std;

#define lm (1<<30)
#define N 200010
#define ff first
#define ss second
#define ll long long
#define pb push_back
#define mod 1000000007
#define pii pair <ll, ll>
#define sz(a) int(a.size())
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
ll bigmod(ll a,ll e) {if(e==0)return 1;ll x=bigmod(a*a%mod,e>>1);return e&1?x*a%mod:x;}

int n;
pii p[N];
int v[N];
int vis[N];
set <vector <int>> S;
vector <int> E[N][5], A;

void dfs(int x)
{
    if(x == n) {
        S.insert(A);
        return;
    }

    if(A.empty()) {
        for(int i = 1; i <= n; i++) {
            if(vis[i]) continue;

            vis[i] = 1;
            A.pb(i);
            dfs(x);
            vis[i] = 0;
            A.pop_back();
        }
    } else {
        int nd = A.back();
        for(auto i: E[nd][v[x]])
            if(vis[i] == 0) {
                vis[i] = 1;
                A.pb(i);
                dfs(x+1);
                vis[i] = 0;
                A.pop_back();
            } 
    }
}

void bit(int x)
{
    if(x == n) {
        dfs(1);

        return;
    }

    for(int i = 0; i < n; i++) {
        v[x] = i;
        bit(x+1);
    }
}

int main()
{
    cin >> n;

    for(int i = 1; i <= n; i++) {
        cin >> v[i];

        int x = v[i], cnt = 0;
        while(x) cnt += x%2, x/=2;

        p[i].ff = cnt;
        x = v[i], cnt = 0;
        while(x) cnt += (x%3 == 1 ? 1 : 0), x/=3;
        p[i].ss = cnt;
    }

    for(int i = 1; i <= n; i++)
        for(int h = 1; h <= n; h++) {
            if(p[i].ff == p[h].ff) E[i][0].pb(h);
            if(p[i].ss == p[h].ss) E[i][1].pb(h);
        }
    
    memset(v, 0, sizeof(v));
    bit(1);

    cout << S.size();
}

Compilation message

beauty.cpp:23: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   23 | #pragma GCC optimization ("O3")
      | 
beauty.cpp:24: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   24 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24576 KB Output is correct
2 Correct 16 ms 24576 KB Output is correct
3 Correct 17 ms 24576 KB Output is correct
4 Correct 16 ms 24576 KB Output is correct
5 Correct 18 ms 24704 KB Output is correct
6 Execution timed out 3071 ms 25212 KB Time limit exceeded
7 Halted 0 ms 0 KB -