SHHV – spoj

Đề bài:

• http://vn.spoj.com/problems/SHHV/

Thuật toán:

• (đang cập nhập)

Code:

• C++

#include 
using namespace std;
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define double db
typedef long long ll;
typedef pair PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
const int MAXN = 13;
const int oo = 1e9+3;
string s;

ll gt[MAXN+1];
int n, x, a[MAXN+1], b[MAXN+1], i, j;
bool chon[MAXN+1];
ll t;

void init() {
    gt[0] = 1;
    gt[1] = 1;
    for (int i=2; i<=MAXN; i++) gt[i] = gt[i-1]*i;
}

void query1() {
    ll ans = 0;
    memset(chon,0,sizeof(chon));
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=a[i]-1; j++)
        if (!chon[j]) {
            ans += gt[n-i];
        }
        chon[a[i]] = 1;
    }
    cout << ans+1 << endl;
}

void query2() {
    memset(chon,0,sizeof(chon));
    t--;
    for (i=1; i<=n; i++) {
        int tmp = 0;
        for (j=1; j<=n; j++) {
            if (!chon[j]) tmp++;
            if (gt[n-i]*tmp>t) break;
        }
        t -= gt[n-i]*(tmp-1);
        b[i] = j;
        chon[j]=1;
    }
    for (int i=1; i<=n; i++) cout << b[i] << " ";
}

int main() {
    	#ifndef ONLINE_JUDGE
    	freopen("test.inp", "r", stdin);
    	freopen("test.out", "w", stdout);
    	#endif
    while (cin>>a[++n]);
    t=a[--n]; n--;
    init();
    query1();
    query2();
    return 0;
}