Submission #403840

#	Time	Username	Problem	Language	Result	Execution time	Memory
403840		yoavL	Koala Game (APIO17_koala)	C++14	33 / 100	62 ms	328 KiB

koala

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <bitset>
#include <math.h>
#include <fstream>
#include <iomanip>
#include "koala.h"

using namespace std;

using ll = int;
using ld = long double;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vvvvll = vector<vvvll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using vld = vector<ld>;
using vstr = vector<string>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
using pb = pair<bool, bool>;
using vpb = vector<pb>;
using vvpb = vector<vpb>;
using vi = vector<int>;
using vvi = vector<vi>;

const ll mod = (ll)1e9 + 7;
const ll inf = (ll)1e18;


#define F           first
#define S           second

#define FAST        ios_base::sync_with_stdio(0)
#define FASTIN		cin.tie(0)
#define FASTOUT		cout.tie(0)

#define upmin(a, b) a = min(a, b)
#define upmax(a, b) a = max(a, b)

#define whatvec(v) cout << #v << ": "; for(auto it = v.begin(); it != v.end(); ++it) cout << *it << " "; cout << endl;
#define prv(v) cout << #v << ": "; for(auto it = v.begin(); it != v.end(); ++it) cout << *it << " "; cout << endl;
#define wpr(x) cout << #x << " = " << (x) << endl;
#define wprv(v) cout << #v << ": "; for(auto it = v.begin(); it != v.end(); ++it) cout << *it << " "; cout << endl;
#define what(x) cout << #x << " = " << (x) << "\n";
#define pr(x) cout <<x << endl;

#define rep(i,s,e) for(ll i = s;i < e; i++)

#define all(x) x.begin(),x.end()
#define pb push_back


const ll len = 100;
const ll maxcap = 20;

ll a[len], b[len];

void fill(ll ind)
{
    for (ll i = 0; i < len; i++) a[i] = 0;
    a[ind] = 1;
}

void pra()
{
    pr("a:");
    rep(i, 0, len) {
        cout << a[i] << " ";
    }
    cout << endl;
}


void prb()
{
    pr("b:");
    rep(i, 0, len) {
        cout << b[i] << " ";
    }
    cout << endl;
}

int minValue(int N, int W) {
    //pr("here");
    // TODO: Implement Subtask 1 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.
    ll n = N, w = W;
    

    //vll a(n, 1);
    fill(0);
    rep(i, 0, len) b[i] = -1;
    bool ok = false;
    playRound(a, b);

    rep(i, 0, len) if (b[i] != -1) ok = true;
    if (!ok) while (true);
    for (ll i = 0; i < len; i++) {
        if (b[i] == 0) return i;
    }
    fill(1);
    playRound(a, b);
    rep(i, 0, len) {
        if (b[i] == 0) return i;
    }
    while (true);
    return 0;
}


int rec(vll ind)
{
    if (ind.size() == 1) {
        return ind[0];
    }
    ll sz = ind.size();
    ll cap = len / sz;
    rep(i, 0, len) {
        a[i] = 0;
    }
    rep(i, 0, sz) {
        a[ind[i]] = cap;
    }
    /*
    pr("a:");
    rep(i, 0, len) {
        cout << a[i] << " ";
    }
    cout << endl;
    */
    playRound(a, b);
    /*
    pr("b:");
    rep(i, 0, len) {
        cout << b[i] << " ";
    }
    cout << endl;
    */
    ll maxv = 0;
    rep(i, 0, len) {
        upmax(maxv, b[i]);
    }
    vll nind;
    rep(i, 0, len) {
        if (b[i] == maxv) nind.push_back(i);
    }
    return rec(nind);
}

int maxValue(int N, int W) {
    // TODO: Implement Subtask 2 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.


    vll ind;
    for (ll i = 0; i < len; i++) ind.push_back(i);
    return rec(ind);
}


int put_v_comp(ll v, ll i1, ll i2)
{
    //wpr(v);
    rep(i, 0, len) {
        a[i] = 0;
    }
    a[i1] = a[i2] = v;

    //pra();
    playRound(a, b);
    //prb();
    if (b[i1] > b[i2]) return 0;
    if (b[i1] < b[i2]) return 1;
    if (b[i1] > 0) return 2;
    return 3;
}






bool comp(ll i, ll j)
{
    
    if (i == j) return 0;
    bool change = 0;
    
    if (i > j) {
        change = 1;
        swap(i, j);
    }
    
    //cout << "comp: " << i << ", " << j << endl;
    
    //return false;
    ll low = 0, high = maxcap, mid = 0;
    while (low <= high) {
        mid = (low + high) / 2;

        ll res = put_v_comp(mid, i, j);
        //wpr(res);
        if (res <= 1) {
            bool tans = res;
            //cout << "returning: " << res << endl;
            if (change) return !tans;
            return tans;
        }
        if (res == 2) {
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }
    //while (true);
    return 0;
}


int greaterValue(int N, int W) {
    // TODO: Implement Subtask 3 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.

    return comp(0, 1);
}

void allValues(int N, int W, int* P) {
    //pr("wasup");
    if (W == 2 * N && false) {
        // TODO: Implement Subtask 4 solution here.
        // You may leave this block unmodified if you are not attempting this
        // subtask.
    }
    else {
        // TODO: Implement Subtask 5 solution here.
        // You may leave this block unmodified if you are not attempting this
        // subtask.
        //pr("hii");
        vll inds(len);
        for (ll i = 0; i < len; i++) {
            inds[i] = i;
        }

        sort(inds.begin(), inds.end(), comp);
        rep(i, 1, len) {
            if (comp(inds[i], inds[i - 1]) != 0) while (true);
        }
        rep(i, 0, len)
        {
            P[i] = inds[i]+1;
        }
        

    }
}


/*


4 1
6 6
5 3 2 1 6 4



3 1
6 6
5 3 2 1 6 4

3 1
6 6
3 5 2 1 6 4


4 1
6 6
5 3 2 1 6 4


4 1
6 6
5 3 2 1 6 4

3 1
6 6
1 2 5 3 6 4


3 1
6 6
5 4 3 2 1


4 1 
6 6 
5 3 2 1 6 4 

5 1
6 6
1 2 5 3 6 4


4 1
6 6
1 2 3 4 5 6


4 1
100 100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 
39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 
74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100


4 1
100 100
100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 
65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 
31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1




4 1
100 100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 
39 40 41 42 43 44 45 46 47 48 49 50 
100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 
65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 



*/

Compilation message (stderr)

koala.cpp: In function 'int minValue(int, int)':
koala.cpp:102:8: warning: unused variable 'n' [-Wunused-variable]
  102 |     ll n = N, w = W;
      |        ^
koala.cpp:102:15: warning: unused variable 'w' [-Wunused-variable]
  102 |     ll n = N, w = W;
      |               ^

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