Submission #3695359


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];
double Sscore[11][N+1];
int64_t C[M+1];
bitset<M+1> used;
vector<int> order[11];
vector<int> zone(11, 0);

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 mn = *min_element(skillLevel+1, skillLevel+N+1);
    if(mn == MAX_SKILL) return -1;
    int i = order[mn+1][0];
    for(int i2 : order[mn+1]) if(skillLevel[i] > skillLevel[i2]) i = i2;
    int64_t money = 10000LL * (1<<(skillLevel[i]+1));
    return (mymoney >= money) ? i : -1;
}

int max_cnt = 0;
void do_skillup(int i, int t, bool test=false){
    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(skillLevel[i] == MAX_SKILL) max_cnt++;
        if(max_cnt == N) skill_max = true;
        //cerr << "turn " << t << " skillLevel[" << i << "] = " << skillLevel[i] << endl;
    }
    if(!test) 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, bool test=false){
    if(i == -1){
        mymoney += 1000;
        if(!test) cout << 3 << endl;
    }else{
        mymoney += payment(i, t);
        used[i] = true;
        if(!test) 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);
    }
    for(int j=1; j<=10; j++){
        for(int i=1; i<=N; i++) order[j].push_back(i);
    }

    int64_t mx = 0;
    for(int t=1; t<=T; t++){
        int skill = check_skillup();
        auto p = find_better_job(t);
        int job = p.first;
        int64_t gain = p.second;

        if(skill == -1 || gain >= mx*1.3){
            do_job(job, t, true);
            mx = max(mx, gain);
        }else{
            do_skillup(skill, t, true);
        }

        if(*max_element(skillLevel+1, skillLevel+N+1) == *min_element(skillLevel+1, skillLevel+N+1)){
            int lv = *max_element(skillLevel+1, skillLevel+N+1);
            if(lv > 0 && zone[lv] == 0) zone[lv] = t;
            if(lv == MAX_SKILL) break;
        }
    }
    for(int i=1; i<=10; i++) cerr << i << " " << zone[i] << endl;

    for(int i=1; i<=M; i++){
        int mx = *max_element(S[i]+1, S[i]+N+1);
        if(mx > 0 && zone[mx-1] <= B[i] && B[i] <= zone[mx]){
            for(int j=1; j<=N; j++) if(S[i][j] == mx) Sscore[mx][j] += C[i];
        }
    }
    for(int j=1; j<=10; j++){
        for(int i=1; i<=N; i++) order[j].push_back(i);
        sort(order[j].begin(), order[j].end(), [&](int i1, int i2){ return Sscore[j][i1] > Sscore[j][i2];});
    }

    mymoney = 0;
    used = 0;
    mx = 0;
    for(int i=1; i<=N; i++){
        skillLevel[i] = 0;
        skillPoint[i] = 0;
    }
    skill_max = false;
    max_cnt = 0;

    int t2 = T+1;
    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 >= mx*1.3){
            do_job(job, t);
            mx = max(mx, gain);
        }else{
            do_skillup(skill, t);
        }
    }

    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 << "money: "<< mymoney << endl;
    return 0;
}

Submission Info

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

Test Cases

Set Name Score / Max Score Test Cases
Sample 1405365.58 / 1000 example_01.txt
All 354653896.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 160 ms 2304 KB
subtask_01_03.txt 161 ms 2304 KB
subtask_01_04.txt 166 ms 2304 KB
subtask_01_05.txt 165 ms 2304 KB
subtask_01_06.txt 163 ms 2304 KB
subtask_01_07.txt 162 ms 2304 KB
subtask_01_08.txt 163 ms 2304 KB
subtask_01_09.txt 165 ms 2304 KB
subtask_01_10.txt 164 ms 2304 KB
subtask_01_11.txt 165 ms 2304 KB
subtask_01_12.txt 166 ms 2304 KB
subtask_01_13.txt 165 ms 2304 KB
subtask_01_14.txt 165 ms 2304 KB
subtask_01_15.txt 163 ms 2304 KB
subtask_01_16.txt 163 ms 2304 KB
subtask_01_17.txt 165 ms 2304 KB
subtask_01_18.txt 164 ms 2304 KB
subtask_01_19.txt 167 ms 2304 KB
subtask_01_20.txt 165 ms 2304 KB
subtask_01_21.txt 165 ms 2304 KB
subtask_01_22.txt 165 ms 2304 KB
subtask_01_23.txt 172 ms 2304 KB
subtask_01_24.txt 163 ms 2304 KB
subtask_01_25.txt 165 ms 2304 KB
subtask_01_26.txt 165 ms 2304 KB
subtask_01_27.txt 167 ms 2304 KB
subtask_01_28.txt 165 ms 2304 KB
subtask_01_29.txt 165 ms 2304 KB
subtask_01_30.txt 162 ms 2304 KB