Submission #249897

#	Time	Username	Problem	Language	Result	Execution time	Memory
249897		sealnot123	Ruins 3 (JOI20_ruins3)	C++14	100 / 100	209 ms	5376 KiB

ruins3

#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
#define FOR(i, a, b) for(int i=(a); i<=(b); ++i)
#define ROF(i, a, b) for(int i=(a); i>=(b); --i)
#define make_unique(a) sort(all((a))), (a).resize(unique(all((a)))-(a).begin())

using namespace std;

typedef pair<int,int> PII;
typedef long long LL;
typedef double DD;
typedef long double LD;
typedef pair<LL,LL> PLL;
typedef pair<DD,DD> PDD;
typedef vector<int> VI;
typedef vector<LL> VL;

const int N = 607;
const int mod = 1000000007;
void plusle(int &a, int b){
    if((a+=b) >= mod) a -= mod;
}
int add(int a, int b){
    return ((a+=b)>=mod) ? a-mod : a;
}
int mul(int a, int b){
    return a * 1ll * b % mod;
}
int dp[N<<1][N];
int comp[N], freestyle[N];
int ranger[N];
int fac[N], inv[N], paskal[N][N];
int place[N][N>>1]; // pillars, sum
int power(int a, int b){
    int ans = 1;
    for(int i = 1; i <= b; i<<=1, a=mul(a,a)){
        if(i&b) ans = mul(ans, a);
    }
    return ans;
}
void init(){
    fac[0] = inv[0] = paskal[0][0] = 1;
    FOR(i, 1, 600){
        fac[i] = mul(fac[i-1], i);
        inv[i] = power(fac[i], mod-2);
        paskal[i][0] = 1;
        FOR(j, 1, i) paskal[i][j] = add(paskal[i-1][j-1], paskal[i-1][j]);
    }
    //printf("[[[%d\n",paskal[2][2]);
    FOR(i, 0, 300) place[0][i] = 1;
    FOR(i, 1, 600){
        FOR(j, 0, 300){
            place[i][j] = 0;
            if(j > 0) place[i][j] = mul( place[i-1][j], i );
            if(i > 1) plusle( place[i][j], mul( mul(paskal[i][2], inv[2]), place[i-2][j+1] ) );
            if(j > 1) plusle( place[i][j], place[i][j-1] );
        }
    }
    //printf("place(2,0) %d\n",place[2][0]);
    comp[1] = 1;
    FOR(i, 2, 600) comp[i] = place[i][0];
    FOR(i, 0, 300) place[0][i] = 1;
    FOR(i, 1, 600){
        FOR(j, 0, 300){
            place[i][j] = 0;
            place[i][j] = mul( place[i-1][j], i );
            if(i > 1) plusle( place[i][j], mul( mul(paskal[i][2], inv[2]), place[i-2][j+1] ) );
            if(j > 0) plusle( place[i][j], place[i][j-1] );
        }
    }
    freestyle[0] = 1;
    FOR(i, 1, 600) freestyle[i] = place[i][0];
    //FOR(i, 0, 5){
    //    printf("comp %d = %d, free %d = %d\n",i,comp[i],i,freestyle[i]);
    //}
    FOR(i, 1, 600){
        // have i arrange index
        // make smth
        FOR(j, 1, i){
            // j is number of pillar in the first component
            int v = mul( paskal[i-1][j-1], comp[j] );
            int w = mul( freestyle[i-j], v );
            plusle( ranger[i], w );
        }
        //if(i <= 5) printf("[%d] %d\n",i,ranger[i]);
    }
}

int mark[N<<1];
void solve(){
    int n;
    init();
    scanf("%d",&n);
    FOR(i,1,n){
        int a; 
        scanf("%d",&a);
        mark[a] = 1;
    }
    dp[(n<<1)+1][0] = 1;
    int Fcnt, Rcnt;
    Fcnt = Rcnt = 0;
    ROF(i, n<<1, 1){
        if(mark[i]){
            FOR(j, 0, Rcnt-Fcnt){
                int remain = Rcnt - Fcnt - j;
                ROF(k, j, 0){
                    int use = j-k;
                    int v = mul( paskal[j][use], ranger[use+1] );
                    plusle(dp[i][k], mul( dp[i+1][j], v ) );
                }
            }
            FOR(j, 0, Rcnt-Fcnt){
                plusle( dp[i][j+1], dp[i+1][j] );
            }
            ++Rcnt;
        }else{
            FOR(j, 0, Rcnt-Fcnt-1){
                int remain = Rcnt - Fcnt - j;
                dp[i][j] = mul(dp[i+1][j], remain);
            }
            ++Fcnt;
        }
        //FOR(j, 0, Rcnt-Fcnt){
        //    printf("(%d, %d) = %d\n",i,j,dp[i][j]);
        //}
    }
    printf("%d",dp[1][0]);
}

int main(){
    solve();
	return 0;
}
/*
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

Compilation message (stderr)

ruins3.cpp: In function 'void solve()':
ruins3.cpp:110:21: warning: unused variable 'remain' [-Wunused-variable]
                 int remain = Rcnt - Fcnt - j;
                     ^~~~~~
ruins3.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
ruins3.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a);
         ~~~~~^~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 52 / 52
• Subtask 3: 42 / 42