Submission #1169020

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169020		12345678	Koala Game (APIO17_koala)	C++20	75 / 100	33 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, int a, int b)
{
    qrs[a]=qrs[b]=x;
    playRound(qrs, ans);
    if (ans[a]<=qrs[a]&&ans[b]>qrs[b]) return -2;
    if (ans[a]>qrs[a]&&ans[b]<=qrs[b]) return -1;
    if (ans[a]<=qrs[a]||ans[b]<=qrs[b]) return 1;
    return 0;
}

int greatervalue(int N, int W, int x, int y)
{
    // 1 when first is greater
    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, x, y);
        if (tmp==-1) return 1;
        if (tmp==-2) return 0;
        if (tmp) r=md-1;
        else l=md+1;
    }
    solve(l, qrs, ans, x, y);
    if (ans[x]>qrs[x]) return 1;
    else return 0;
}

int greaterValue(int N, int W) {
    return greatervalue(N, W, 1, 0);
}

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

bool comparesub4(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;
}

bool maincompare(int i, int j, int t)
{
    if (!t) return comparesub4(i, j);
    else return greatervalue(n, w, j, i);
}

void mergesort(int l, int r, int t)
{
    if (l==r) return;
    int md=(l+r)/2, idxl=l, idxr=md+1, idx=l;
    mergesort(l, md, t);
    mergesort(md+1, r, t);
    while (idxl<=md||idxr<=r)
    {
        if (idxl>md) tmp[idx++]=srt[idxr++];
        else if (idxr>r) tmp[idx++]=srt[idxl++];
        else if (maincompare(srt[idxl], srt[idxr], t)) 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;
    w=W;
    for (int i=0; i<N; i++) srt[i]=i;
    if (W >= 2*N) {
        mergesort(0, N-1, 0);
    } else {
        mergesort(0, N-1, 1);
    }
    for (int i=0; i<N; i++) P[srt[i]]=i+1;
}

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