Submission #1282944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282944		dosts	Koala Game (APIO17_koala)	C++20	100 / 100	36 ms	460 KiB

koala

#include "koala.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
//#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;

int minValue(int N, int W) {
    int B[N],R[N];
    B[0] = 1;
    for (int j = 1;j<N;j++) B[j] = 0;
    playRound(B,R);
    for (int j = 1;j<N;j++) {
        if (!R[j]) return j;
    }
    B[1] = 1;
    B[0] = 0;
    playRound(B,R);
    if (!R[0]) return 0;
    for (int j = 1;j<N;j++) {
        if (!R[j]) return j;
    }
    return -1;
}


int maxValue(int N, int W) {
    assert(N == W  && W == 100);
    int B[N]{},R[N]{};
    for (int i = 0;i<N;i++) B[i] = 1;
    vi top50;
    playRound(B,R);
    for (int i = 0;i<N;i++) if (R[i] == 2) top50.push_back(i);
    for (int i = 0;i<N;i++) B[i] = 0;
    for (auto it : top50) B[it] = 2; 
    playRound(B,R);
    vi top25;
    for (int i = 0;i<N;i++) if (R[i] == 3) top25.push_back(i);
    for (int i = 0;i<N;i++) B[i] = 0;
    for (auto it : top25) B[it] = 4; 
    playRound(B,R);
    vi top9;
    for (int i = 0;i<N;i++) if (R[i] == 5) top9.push_back(i);
    for (int i = 0;i<N;i++) B[i] = 0;
    for (auto it : top9) B[it] = 11; 
    playRound(B,R);
    for (int i = 0;i<N;i++) if (R[i] == 12) return i;
}

int greaterValue(int N, int W) {
    int B[N]{},R[N];
    int l = 1;
    int r = min(9,N/2);
    while (l<=r) {
        int mid = (l+r) >> 1;
        B[0] = B[1] = mid;
        playRound(B,R);
        if ((R[0] > mid) != (R[1] > mid)) return R[0] < R[1];
        if (R[0] > mid) l = mid+1;
        else r = mid-1;
    }
}
int greaterValue2(int N,int a,int b) {
    int B[N]{},R[N];
    int l = 1;
    int r = min(9,N/2);
    while (l<=r) {
        int mid = (l+r) >> 1;
        B[a] = B[b] = mid;
        playRound(B,R);
        if ((R[a] > mid) != (R[b] > mid)) return R[a] < R[b];
        if (R[a] > mid) l = mid+1;
        else r = mid-1;
    }
}

int greaterValue3(int N,int a,int b) {
    int B[N]{},R[N];
    B[a] = B[b] = N-1;
    playRound(B,R);
    if (R[a] > N-1) return 0;
    return 1;
}

void mergesort1(int* P,int l,int r,const int N) {
    if (l == r) {
        P[l] = 1;
        return;
    }
    int m = (l+r) >> 1;
    mergesort1(P,l,m,N);
    mergesort1(P,m+1,r,N);
    vector<pii> sol,sag;
    for (int j = l;j<=m;j++) sol.push_back({P[j],j});
    for (int j = m+1;j<=r;j++) sag.push_back({P[j],j});
    sort(all(sol)),sort(all(sag));
    int ctr = 1;
    int ptr1 = 0,ptr2 = 0;
    while (ptr1 != big(sol) || ptr2 != big(sag)) {
        if (ptr1 == big(sol)) P[sag[ptr2++].ss] = ctr++;
        else if (ptr2 == big(sag)) P[sol[ptr1++].ss] = ctr++;
        else {
            if (greaterValue3(N,sol[ptr1].ss,sag[ptr2].ss)) P[sol[ptr1++].ss] = ctr++;
            else P[sag[ptr2++].ss] = ctr++;
        }
    }
}

int nn;

int rooty(int x) {
    for (int i = nn-1;i>=1;i--) {
        if (i*i<=x) return i;
    }
}

void dnq(int* P,vi& pos,int l,int r) {
    if (l == r) {
        assert(big(pos) == 1);
        P[pos[0]] = l;
        return;
    }
    int splitshit = min(nn/(r-l+1),rooty(2*l));
    int B[nn]{},R[nn];
    for (auto it : pos) B[it] = splitshit;
    playRound(B,R);
    vi great,smal;
    for (auto it : pos) {
        if (R[it] > splitshit) great.push_back(it);
        else smal.push_back(it);
    }
    dnq(P,smal,l,l+big(smal)-1);
    dnq(P,great,l+big(smal),r);
}

void allValues(int N, int W, int *P) {
    nn = N;
    if (W == 2*N) mergesort1(P,0,N-1,N);
    else {
        vi pos;
        for (int j = 0;j<N;j++) pos.push_back(j);
        dnq(P,pos,1,N);
    }
}

Compilation message (stderr)

koala.cpp: In function 'int maxValue(int, int)':
koala.cpp:56:1: warning: control reaches end of non-void function [-Wreturn-type]
   56 | }
      | ^
koala.cpp: In function 'int greaterValue(int, int)':
koala.cpp:70:1: warning: control reaches end of non-void function [-Wreturn-type]
   70 | }
      | ^
koala.cpp: In function 'int greaterValue2(int, int, int)':
koala.cpp:83:1: warning: control reaches end of non-void function [-Wreturn-type]
   83 | }
      | ^
koala.cpp: In function 'int rooty(int)':
koala.cpp:123:1: warning: control reaches end of non-void function [-Wreturn-type]
  123 | }
      | ^

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