Submission #1168968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168968		12345678	Koala Game (APIO17_koala)	C++20	47 / 100	32 ms	464 KiB

koala

#include "koala.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=1e2+5;

int minValue(int N, int W) {
    int qrs[nx], ans[nx];
    for (int i=0; i<N; i++) qrs[i]=(i==0);
    playRound(qrs, ans);
    for (int i=1; i<N; i++) if (ans[i]==0) return i;
    return 0;
}

int maxValue(int N, int W) {
    int qrs[nx], ans[nx], per, t=4;
    vector<int> idx, nidx;
    for (int i=0; i<N;i ++) idx.push_back(i);
    while (t--)
    {
        per=W/idx.size();
        for (int i=0; i<N; i++) qrs[i]=0;
        for (auto x:idx) qrs[x]=per;
        playRound(qrs, ans);
        for (int i=0; i<N; i++) if (qrs[i]>0&&ans[i]>qrs[i]) nidx.push_back(i);
        idx=nidx;
        nidx.clear();
    }
    return idx[0];
}

int solve(int x, int *qrs, int *ans)
{
    qrs[0]=qrs[1]=x;
    playRound(qrs, ans);
    if (ans[0]<=qrs[0]&&ans[1]>qrs[1]) return -1;
    if (ans[0]>qrs[0]&&ans[1]<=qrs[1]) return -2;
    if (ans[0]<=qrs[0]||ans[1]<=qrs[1]) return 1;
    return 0;
}

int greaterValue(int N, int W) {
    int qrs[nx], ans[nx];
    for (int i=0; i<N; i++) qrs[i]=0;
    int l=1, r=10;
    while (l<r)
    {
        int md=(l+r)/2;
        int tmp=solve(md, qrs, ans);
        if (tmp==-1) return 1;
        if (tmp==-2) return 0;
        if (tmp) r=md-1;
        else l=md+1;
    }
    solve(l, qrs, ans);
    if (ans[0]>qrs[0]) return 0;
    else return 1;
}

int srt[nx], tmp[nx], n;

bool compare(int i, int j)
{
    int qrs[nx], ans[nx];
    for (int k=0; k<n; k++) qrs[k]=0;
    qrs[i]=qrs[j]=100;
    playRound(qrs, ans);
    if (ans[i]<=qrs[i]) return 1;
    else return 0;
}

void mergesort(int l, int r)
{
    if (l==r) return;
    int md=(l+r)/2, idxl=l, idxr=md+1, idx=l;
    mergesort(l, md);
    mergesort(md+1, r);
    while (idxl<=md||idxr<=r)
    {
        if (idxl>md) tmp[idx++]=srt[idxr++];
        else if (idxr>r) tmp[idx++]=srt[idxl++];
        else if (compare(srt[idxl], srt[idxr])) tmp[idx++]=srt[idxl++];
        else tmp[idx++]=srt[idxr++];
    }
    for (int i=l; i<=r; i++) srt[i]=tmp[i]; //cout<<"debug "<<l<<' '<<r<<' '<<srt[i]<<'\n';
}

void allValues(int N, int W, int *P) {
    n=N;
    if (W >= 2*N) {
        for (int i=0; i<N; i++) srt[i]=i;
        mergesort(0, N-1);
        for (int i=0; i<N; i++) P[srt[i]]=i+1;
    } else {
        // TODO: Implement Subtask 5 solution here.
        // You may leave this block unmodified if you are not attempting this
        // subtask.
    }
}

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 0 / 53