Submission #1361449

#TimeUsernameProblemLanguageResultExecution timeMemory
1361449yyc000123Monster-Go (EGOI25_monstergo)C++20
100 / 100
0 ms344 KiB
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
#define g0 get<0>
#define g1 get<1>
#define g2 get<2>
const int N = 55 ;
vector<tuple<int,int,int>> vp[3] = {{{13,13,1},{7,14,2},{5,15,3},{4,16,4},{3,18,6},{1,12,12}},{{28,16,2},{15,18,3}},{{35,21,3}}} ;
int dp[N] , n , cnt ;
pair<int,int> from[N] ;

void f1(){
    for(int i=cnt ; i<cnt+12 ; i++) cout << i << ' ' ; cout << '\n' ;
}

void f(int per , int skip){
    int temp = 12/per+skip ;
    for(int i=0 ; i<temp ; i++){
        for(int j=i+(skip>=2) ; j<temp ; j++){
            for(int l=j+(skip>=3) ; l<temp ; l++){
                for(int k=0 ; k<temp ; k++){
                    if(skip==1 && k==i) continue ;
                    else if(skip==2 && (k==i || k==j)) continue ;
                    else if(skip==3 && (k==i || k==j || k==l)) continue ;
                    for(int m=0 ; m<per ; m++) cout << cnt+k*per+m << ' ' ;
                }
                cout << '\n' ;
                if(skip<3) break ;
            }
            if(skip<2) break ;
        }
    }
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) ;
    memset(dp,0x3f,sizeof(dp)) ;
    dp[0]=0 ;
    for(int i=1 ; i<=50 ; i++){
        for(int j=0 ; j<3 ; j++){
            for(int l=0 ; l<vp[j].size() ; l++){
                if(i-g0(vp[j][l])>=0){
                    if(dp[i-g0(vp[j][l])]+g1(vp[j][l])<dp[i]) from[i]={j,l} ;
                    dp[i]=min(dp[i],dp[i-g0(vp[j][l])]+g1(vp[j][l])) ;
                }
            }
        }
    }
    // int tempcnt = 0 ; for(int i=1 ; i<=50 ; i++) if(dp[i]<=50) tempcnt++ ; cout << tempcnt << '\n' ; //
    // for(int i=1 ; i<=50 ; i++) cout << dp[i] << ' ' ; cout << '\n' ; return 0 ; //
    // for(int i=1 ; i<=50 ; i++) cout << from[i].first << ' ' << from[i].second << '\n' ; return 0 ; //
    cin >> n ;
    while(n){
        if(g0(vp[from[n].first][from[n].second])==1) f1() ;
        else f(g2(vp[from[n].first][from[n].second]),from[n].first+1) ;
        cnt+=g1(vp[from[n].first][from[n].second]) ;
        n-=g0(vp[from[n].first][from[n].second]) ;
    }
    return 0 ;
}
#Result Execution timeMemoryGrader output
Fetching results...