Submission #256467

#	Time	Username	Problem	Language	Result	Execution time	Memory
256467		maximath_1	Koala Game (APIO17_koala)	C++11	100 / 100	79 ms	512 KiB

koala

#include "koala.h"
#include <bits/stdc++.h>
using namespace std;
 
int a[105], b[105];
 
int minValue(int n, int w){
    for(int i = 1; i < n; i ++)
        a[i] = 0;
    a[0] = 1;
    playRound(a, b);
    for(int i = 0; i < n; i ++)
        if(a[i] >= b[i]) return i;
    return 0;
}
 
vector<int> large;
int maxValue(int n, int w){
    large.clear();
    for(int i = 0; i < n; i ++)
        large.push_back(i);
    for(; large.size() > 1;){
        for(int i = 0; i < n; i ++)
            a[i] = 0;
        int ct = w / large.size();
        for(int i : large)
            a[i] = ct;
 
        playRound(a, b);
 
        large.clear();
        for(int i = 0; i < n; i ++)
            if(b[i] > ct)
                large.push_back(i);
    }
    return large[0];
}
 
int n, w;
bool cmp(int x, int y){
    int lf = 1, rg = min(w / 2, 12);
    for(int md; lf <= rg;){
        md = (lf + rg) / 2;
        for(int i = 0; i < n; i ++)
            a[i] = 0;
        a[x] = a[y] = md;
        playRound(a, b);
        bool gt0 = b[x] > a[x];
        bool gt1 = b[y] > a[y];
        if(gt0 == gt1){
            if(gt1) lf = md + 1;
            else rg = md - 1;
        }else{
            if(gt1) return 1;
            else return 0;
        }
    }
    return 0;
}
 
int greaterValue(int N, int W){
    n = N, w = W;
    return cmp(0, 1);
}
 
int every[105];
 
void solve(int n, int w, vector<int> v, int l, int r){
    if(l > r) return;
    if(l == r) return void(every[v[0]] = l);
    int ct = min((int)sqrt(2 * l), min(w / (r - l + 1), 8));
 
    for(int i = 0; i < n; i ++)
        a[i] = 0;
    for(int i : v)
        a[i] = ct;
    playRound(a, b);
    vector<int> lf, rg;
    for(int i : v){
        if(b[i] > ct) rg.push_back(i);
        else lf.push_back(i);
    }
 
    solve(n, w, lf, l, l + (int)lf.size() - 1);
    solve(n, w, rg, r - (int)rg.size() + 1, r);
}
 
void allValues(int N, int W, int *P){
    n = N, w = W;
    if(W == N * 2){
        //sub4
        vector<int> tmp(n);
        for(int i = 0; i < n; i ++)
            tmp[i] = i;
        stable_sort(tmp.begin(), tmp.end(), [&](int x, int y){
            for(int i = 0; i < n; i ++) a[i] = 0;
            a[x] = a[y] = n;
            playRound(a, b);
            return b[x] < b[y];
        });
        for(int i = 0; i < n; i ++){
            for(int j = 0; j < n; j ++)
                if(tmp[j] == i) P[i] = j + 1;
        }
    }else{
        //sub5
        vector<int> v(n);
        iota(v.begin(), v.end(), 0);
        solve(n, w, v, 1, n);
        for(int i = 0; i < n; i ++)
            P[i] = every[i];
    }
}

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