Submission #3694211


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

const int T = 1000, N = 10, M = 30000;
int A[M+1], B[M+1], S[M+1][N+1];
int64_t C[M+1];
bitset<M+1> used;

vector<int> end2i[T+1];

int skillLevel[N+1];
int skillPoint[N+1];
int64_t mymoney = 0;
bool skill_max = false;

const int MAX_SKILL = 10;
int check_skillup(){
    int i = 1;
    for(int i2=2; i2<=N; i2++) if(skillLevel[i] > skillLevel[i2]) i = i2;
    if(skillLevel[i] == MAX_SKILL) return -1;
    int64_t money = 10000LL * (1<<(skillLevel[i]+1));
    return (mymoney >= money) ? i : -1;
}

void do_skillup(int i){
    int64_t money = 10000LL * (1<<(skillLevel[i]+1));
    assert(mymoney >= money);
    mymoney -= money;
    skillPoint[i]++;
    if(skillPoint[i] == skillLevel[i]+1){
        skillLevel[i]++;
        skillPoint[i] = 0;
        if(i == N && skillLevel[i] == MAX_SKILL) skill_max = true;
    }
    cout << "1 " << i << endl;
}

int64_t payment(int i, int t){
    if(t < A[i] || t > B[i]) return 0;
    double AddMoney = C[i];
    AddMoney *= (1 + 9 * (double)(t - A[i]) / (B[i] - A[i]));
    int SkillLack = 0;
    for (int j = 1; j <= N; j++) SkillLack += max(0, S[i][j] - skillLevel[j]);

    if (SkillLack == 0) AddMoney *= 10;
    else {
        AddMoney *= pow(0.5, SkillLack);
        AddMoney += 1e-9;
    }
    return (int64_t) AddMoney;
}

pair<int, int64_t> find_best_job(int t){
    int mxi = -1;
    int64_t mx = 1000;
    for(int t2=t; t2<=T; t2++){
        for(int i : end2i[t2]){
            if(used[i]) continue;
            int64_t result = payment(i, t);
            if(mx < result){
                mxi = i;
                mx = result;
            }
        }
    }
    return {mxi, mx};
}

pair<int, int64_t> find_better_job(int t){
    int mxi = -1;
    int64_t mx = 1000;
    for(int t2=t; t2<=min(T, t+0); t2++){
        for(int i : end2i[t2]){
            if(used[i]) continue;
            int64_t result = payment(i, t);
            if(mx < result){
                mxi = i;
                mx = result;
            }
        }
    }
    return {mxi, mx};
}

void do_job(int i, int t){
    if(i == -1){
        mymoney += 1000;
        cout << 3 << endl;
    }else{
        mymoney += payment(i, t);
        used[i] = true;
        cout << "2 " << i << endl;
    }
}

int main(){
    int _;
    cin >> _ >> _ >> _;
    for(int i=1; i<=M; i++){
        cin >> A[i] >> B[i] >> C[i];
        for(int j=1; j<=N; j++) cin >> S[i][j];
        end2i[B[i]].push_back(i);
    }

    int t2 = T+1;
    int64_t prev = 0;
    for(int t=1; t<=T; t++){
        if(skill_max){
            cerr << "turn " << t << "  skilllevel max" << endl;
            t2 = t;
            break;
        }

        int skill = check_skillup();
        auto p = find_better_job(t);
        int job = p.first;
        int64_t gain = p.second;

        if(skill == -1 || gain >= prev*1.5){
        //if(skill == -1){
            do_job(job, t);
            prev = gain;
        }else{
            do_skillup(skill);
        }
    }

    int ans[T+1];
    for(int t=T; t>=t2; t--){
        auto p = find_best_job(t);
        ans[t] = p.first;
        mymoney += p.second;
        used[p.first] = true;
    }

    for(int t=t2; t<=T; t++){
        if(ans[t] == -1){
            cout << 3 << endl;
        }else{
            cout << "2 " << ans[t] << endl;
        }
    }

    cerr << "skill:" << endl;
    for(int i=1; i<=N; i++){
        cerr << i << " " << skillLevel[i] << endl;
    }
    cerr << "money: "<< mymoney << endl;
    return 0;
}

Submission Info

Submission Time
Task A - モンスターテイマー
User betrue12
Language C++14 (GCC 5.4.1)
Score 340227566.65
Code Size 3654 Byte
Status
Exec Time 169 ms
Memory 2304 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 1395679.82 / 1000 example_01.txt
All 338831886.83 / 30000 example_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt, subtask_01_19.txt, subtask_01_20.txt, subtask_01_21.txt, subtask_01_22.txt, subtask_01_23.txt, subtask_01_24.txt, subtask_01_25.txt, subtask_01_26.txt, subtask_01_27.txt, subtask_01_28.txt, subtask_01_29.txt, subtask_01_30.txt
Case Name Status Exec Time Memory
example_01.txt 165 ms 2304 KB
subtask_01_02.txt 162 ms 2304 KB
subtask_01_03.txt 161 ms 2304 KB
subtask_01_04.txt 164 ms 2304 KB
subtask_01_05.txt 163 ms 2304 KB
subtask_01_06.txt 163 ms 2304 KB
subtask_01_07.txt 164 ms 2304 KB
subtask_01_08.txt 162 ms 2304 KB
subtask_01_09.txt 165 ms 2304 KB
subtask_01_10.txt 166 ms 2304 KB
subtask_01_11.txt 163 ms 2304 KB
subtask_01_12.txt 164 ms 2304 KB
subtask_01_13.txt 164 ms 2304 KB
subtask_01_14.txt 164 ms 2304 KB
subtask_01_15.txt 167 ms 2304 KB
subtask_01_16.txt 161 ms 2304 KB
subtask_01_17.txt 164 ms 2304 KB
subtask_01_18.txt 164 ms 2304 KB
subtask_01_19.txt 162 ms 2304 KB
subtask_01_20.txt 166 ms 2304 KB
subtask_01_21.txt 166 ms 2304 KB
subtask_01_22.txt 164 ms 2304 KB
subtask_01_23.txt 165 ms 2304 KB
subtask_01_24.txt 166 ms 2304 KB
subtask_01_25.txt 163 ms 2304 KB
subtask_01_26.txt 164 ms 2304 KB
subtask_01_27.txt 165 ms 2304 KB
subtask_01_28.txt 166 ms 2304 KB
subtask_01_29.txt 169 ms 2304 KB
subtask_01_30.txt 161 ms 2304 KB