oj.uz

Submission #1030478

# Submission time Handle Problem Language Result Execution time Memory
1030478 2024-07-22T05:38:35 Z caterpillow Koala Game (APIO17_koala) C++17
19 / 100
 14 ms 456 KB 
#include <bits/stdc++.h>

using namespace std;

using db = long double;
using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end() 
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
const ll INF = 1e18;
const int inf = 1e9;

template<typename... Args> // tuples
ostream& operator<<(ostream& os, tuple<Args...> t) { 
    apply([&](Args... args) { string dlm = "{"; ((os << dlm << args, dlm = ", "), ...); }, t);
    return os << "}";
}

template<typename T, typename V> // pairs
ostream& operator<<(ostream& os, pair<T, V> p) { return os << "{" << p.f << ", " << p.s << "}"; }

template<class T, class = decltype(begin(declval<T>()))> // iterables
typename enable_if<!is_same<T, string>::value, ostream&>::type operator<<(ostream& os, const T& v) {
    string dlm = "{";
    for (auto& i : v) os << dlm << i, dlm = ", ";
    return os << "}";  
}

template <typename T, typename... V>
void printer(string pfx, const char *names, T&& head, V&& ...tail) {
    int i = 0;
    while (names[i] && names[i] != ',') i++;
    constexpr bool is_str = is_same_v<decay_t<T>, const char*>;
    if (is_str) cerr << " " << head;
    else cerr << pfx, cerr.write(names, i) << " = " << head; 
    if constexpr (sizeof...(tail)) printer(is_str ? "" : ",", names + i + 1, tail...);
    else cerr << endl;
}

// #ifdef LOCAL
#define dbg(...) printer(to_string(__LINE__) + ": ", #__VA_ARGS__, __VA_ARGS__)
// #else
// #define dbg(x...)
// #define cerr if (0) std::cerr
// #endif

#include "koala.h"

/*

you have a permutation
each element costs 1, and you can increase costs by up to W
koala will do like a knapsack on these costs and weights 
and u will see the result

w is basically always 100 (or 200)

subtask 1: find the min value (n = w)
    randomly place a stone at say x
    koala can always take 99 stones
    if she takes x, it means the untaken stone is the min
    if she doesnt take x, then x is the min

subtask 2: max vlaue (n = w)
    place one on each element
    koala will take the top 50 best items
    block off all the bad items, and then 

*/

const int n = 100;
int _a[n], _b[n];
vt<int> query(vt<int> a) {
    F0R (i, n) _a[i] = a[i];
    playRound(_a, _b);
    vt<int> res(n); F0R (i, n) res[i] = _b[i];
    return res;
}

int minValue(int N, int W) {
    // TODO: Implement Subtask 1 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.
    vt<int> q(n);
    q[0] = 1;
    auto res = query(q);
    if (res[0] == 2) return find(all(res), 0) - res.begin();
    else return 0;
}

// spamming stones on the 
int maxValue(int N, int n) {
    vt<int> poss(n);
    iota(all(poss), 0);
    F0R (i, 4) {
        vt<int> q(n);
        F0R (_, n / size(poss)) {
            for (int j : poss) {
                q[j]++;
            }
        }
        poss.clear();
        auto res = query(q);
        F0R (i, n) {
            if (res[i] > 1) poss.pb(i);
        }
    }
    return poss[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 0;
}

void allValues(int N, int W, int *P) {
    if (W == 2*N) {
        // 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.
    }
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 3 ms 344 KB Output is correct
3 Correct 3 ms 344 KB Output is correct
4 Correct 3 ms 344 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 456 KB Output is correct
2 Correct 10 ms 340 KB Output is correct
3 Correct 14 ms 456 KB Output is correct
4 Correct 10 ms 344 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -