Submission #1366186

#TimeUsernameProblemLanguageResultExecution timeMemory
1366186weedywelonMonster-Go (EGOI25_monstergo)C++20
100 / 100
0 ms344 KiB
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <limits.h>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <deque>
#include <map>
#include <chrono>
#include <random>
#include <bitset>
#include <tuple>
#define SZ(x) int(x.size())
#define FR(i,a,b) for(int i=(a);i<(b);++i)
#define FOR(i,n) FR(i,0,n)
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define A first
#define B second
#define mp(a,b) make_pair(a,b)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef unsigned __int128 U128;
typedef __int128 I128;
typedef std::pair<int,int> PII;
typedef std::pair<LL,LL> PLL;
using namespace std;

const int MAXN=51, K=12, INF=1e9;
PII p[MAXN];
pair<int,PII> pre[MAXN];
int dp[MAXN];

int c(int a, int b){
    if (b>a) return 0;
    if (b>a-b) b=a-b;
    LL res=1;
    FR(i,1,b+1){
        res=res*(a+1-i)/i;
        if (res>50) return 51;
    }
    return (int)res;
}


void gen(int idx, int taken, int need, int num, vector<int>& cur, const vector<vector<int> >& chunk, int off, vector<vector<int> >& ans){
    if (taken==need){
        vector<int> row;
        for (int id:cur){
            for (int x: chunk[id]){
                row.push_back(off+x);
            }
        }
        ans.push_back(row);
        return;
    }

    for (int i=idx; i<num; i++){
        cur.push_back(i);
        gen(i+1, taken+1, need, num, cur, chunk, off, ans);
        cur.pop_back();
    }
}

signed main(){
    FAST;
    FOR(i,MAXN) p[i]=mp(INF, INF);
    p[1]=mp(12,1);

	int div[6]={1,2,3,4,6,12};
    FOR(j,6){
		int d=div[j];
        for (int s=K+d; s<=50; s+=d){
            int blocks=s/d, need=K/d;

            int cnt=c(blocks, need);
            if (cnt>50) break;
            p[cnt]=min(p[cnt], mp(s,d));
        }
    }

    FOR(i,MAXN){
		dp[i]=INF;
		pre[i]=mp(0,mp(0,0));
	}
    dp[0]=0;

    FR(x,1,51){
        FR(c,1,x+1){
            if (p[c].A==INF) continue;
            if (dp[x-c]+p[c].A<dp[x]){
				if (dp[x-c]==INF) continue;
                dp[x]=dp[x-c]+p[c].A;
                pre[x]=mp(c, p[c]);
            }
        }
    }

    int n; cin>>n;
    vector<vector<int> > ans;
    int off=0;

    while (n>0){
        pair<int,PII> hi=pre[n];
        int c=hi.A, s=hi.B.A, d=hi.B.B;
        int num=s/d, need=K/d;

        vector<vector<int> > chunk;
        for (int i=0; i<s; i+=d){
            vector<int> tmp;
            FOR(j,d) tmp.push_back(i+j);
            chunk.push_back(tmp);
        }

        vector<int> cur;
        gen(0, 0, need, num, cur, chunk, off, ans);
        off+=s;
        n-=c;
    }

	//cout<<SZ(ans)<<"\n";
    for (vector<int> row: ans){
        for (int x: row) cout<<x<<" ";
        cout<<"\n";
    }
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...