oj.uz

Submission #200840

# Submission time Handle Problem Language Result Execution time Memory
200840 2020-02-08T09:45:30 Z BThero Koala Game (APIO17_koala) C++17
43 / 100
 109 ms 504 KB 
// Why am I so dumb? :c
// chrono::system_clock::now().time_since_epoch().count()
                                                  
#include<bits/stdc++.h>
#include "koala.h"
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>

#define pb push_back
#define mp make_pair

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

#define fi first
#define se second

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;   
typedef pair<int, int> pii;
//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int n, w;

int minValue(int N, int W) {
    int me[N], you[N];

    for (int i = 0; i < N; ++i) {
        me[i] = 0;
    }

    me[0] = 1;
    playRound(me, you);
    int i = 0;

    while (you[i]) {
        ++i;
    }

    return i;
}

int maxValue(int N, int W) {
    int me[N], you[N];
    vector<int> v;

    for (int i = 0; i < N; ++i) {
        v.pb(i);
    }

    while (v.size() > 1) {
        int sz = v.size();
        int k = (W + sz) / sz - 1;
        fill(me, me + N, 0);
                
        // v.size() > k

        for (int x : v) {
            me[x] = k;
        }

        playRound(me, you);

        vector<int> nv;

        for (int x : v) {
            if (you[x] > me[x]) {
                nv.pb(x);
            }
        }

        assert(!nv.empty());
        v = nv;            
    }
    
    return v[0];
}

int greaterValue(int N, int W) {
    int me[N], you[N];

    for (int i = 0; i < N; ++i) {
        me[i] = you[i] = 0;
    }

    int L = 1, R = min(W / 2, 8);

    while (L <= R) {
        int x = (L + R) >> 1;
        me[0] = me[1] = x;
        playRound(me, you);

        if (you[0] != you[1]) {
            return you[1] > you[0];
        }

        if (you[0] > 0) {
            L = x + 1;
        }
        else {
            R = x - 1;
        }
    }
}

bool cmp(int a, int b) {
    int me[n], you[n];
    fill(me, me + n, 0);
    me[a] = n;
    me[b] = n;
    playRound(me, you);
    return you[b] > me[b];
}

vector<int> solve(int l, int r) {
    if (l == r) {
        return vector<int>(1, l);
    }

    int m = (l + r) >> 1;
    vector<int> a = solve(l, m);
    vector<int> b = solve(m + 1, r);
    vector<int> ret;    
    int ptr = 0;

    for (int i = 0; i < a.size(); ++i) {
        while (ptr < b.size() && cmp(b[ptr], a[i])) {
            ret.pb(b[ptr++]);
        }

        ret.pb(a[i]);
    }

    while (ptr < b.size()) {
        ret.pb(b[ptr++]);
    }

    return ret;
}

void allValues(int N, int W, int *P) {
    n = N;
    w = W;

    if (w == 2 * n) {
        vector<int> v = solve(0, n - 1);

        for (int i = 0; i < v.size(); ++i) {
            P[v[i]] = i + 1;
        }
    } 
    else {
    
    }
}

Compilation message

koala.cpp: In function 'std::vector<int> solve(int, int)':
koala.cpp:127:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a.size(); ++i) {
                     ~~^~~~~~~~~~
koala.cpp:128:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (ptr < b.size() && cmp(b[ptr], a[i])) {
                ~~~~^~~~~~~~~~
koala.cpp:135:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (ptr < b.size()) {
            ~~~~^~~~~~~~~~
koala.cpp: In function 'void allValues(int, int, int*)':
koala.cpp:149:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < v.size(); ++i) {
                         ~~^~~~~~~~~~
koala.cpp: In function 'int greaterValue(int, int)':
koala.cpp:105:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 376 KB Output is correct
2 Correct 10 ms 248 KB Output is correct
3 Correct 10 ms 376 KB Output is correct
4 Correct 10 ms 248 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 376 KB Output is correct
2 Correct 23 ms 376 KB Output is correct
3 Correct 22 ms 336 KB Output is correct
4 Correct 23 ms 376 KB Output is correct

Subtask #3
14.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 95 ms 356 KB Output is partially correct
2 Partially correct 109 ms 248 KB Output is partially correct
3 Partially correct 92 ms 248 KB Output is partially correct
4 Partially correct 92 ms 504 KB Output is partially correct
5 Partially correct 92 ms 248 KB Output is partially correct
6 Partially correct 93 ms 248 KB Output is partially correct
7 Partially correct 91 ms 248 KB Output is partially correct
8 Partially correct 92 ms 248 KB Output is partially correct
9 Partially correct 93 ms 248 KB Output is partially correct
10 Partially correct 90 ms 372 KB Output is partially correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 248 KB Output is correct
2 Correct 51 ms 312 KB Output is correct
3 Correct 50 ms 248 KB Output is correct
4 Correct 49 ms 312 KB Output is correct
5 Correct 49 ms 380 KB Output is correct
6 Correct 48 ms 248 KB Output is correct
7 Correct 49 ms 248 KB Output is correct
8 Correct 48 ms 248 KB Output is correct
9 Correct 48 ms 376 KB Output is correct
10 Correct 47 ms 376 KB Output is correct
11 Correct 48 ms 248 KB Output is correct
12 Correct 30 ms 300 KB Output is correct
13 Correct 49 ms 252 KB Output is correct
14 Correct 45 ms 376 KB Output is correct
15 Correct 46 ms 376 KB Output is correct
16 Correct 42 ms 248 KB Output is correct
17 Correct 43 ms 376 KB Output is correct
18 Correct 44 ms 248 KB Output is correct
19 Correct 45 ms 332 KB Output is correct
20 Correct 45 ms 252 KB Output is correct

Subtask #5
0 / 53.0

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