oj.uz

Submission #701295

# Submission time Handle Problem Language Result Execution time Memory
701295 2023-02-20T19:39:56 Z Abrar_Al_Samit Koala Game (APIO17_koala) C++17
90 / 100
 473 ms 1048576 KB 
#include "koala.h"
#include<bits/stdc++.h>

using namespace std;

int lim[101];
int minValue(int N, int W) {
    int B[N], R[N];
    for(int i=0; i<N; ++i) {
        B[i] = R[i] = 0;
    }
    B[0] = 1;
    playRound(B, R);

    if(R[0]<=1) {
        return 0;
    }
    for(int i=1; i<N; ++i) {
        if(R[i]==0) return i;
    }
}

int maxValue(int N, int W) {
    int B[N] = {0}, R[N] = {0};

    set<int>s;
    for(int i=0; i<N; ++i) {
        s.insert(i);
    }

    while(s.size()>1) {
        int val = W / s.size();

        memset(B, 0, sizeof B);
        memset(R, 0, sizeof R);

        for(int x : s) {
            B[x] = val;
        }
        playRound(B, R);

        set<int>new_s;
        for(int i=0; i<N; ++i) if(R[i]>B[i]) {
            if(s.count(i)) new_s.insert(i);
        }
        s = new_s;
    }
    return *s.begin();    
}

int greaterValue(int N, int W) {
    int B[N] = {0}, R[N] = {0};

    int l = 1, r = 13;

    while(l<r) {
        int mid = (l+r)/2;

        B[0] = B[1] = mid;
        playRound(B, R);

        if(B[0]<R[0] && B[1]<R[1]) {
            l = mid+1;
        } else if(B[0]>=R[0] && B[1]>=R[1]) {
            r = mid-1;
        } else {
            if(R[0]>B[0]) return 0;
            return 1;            
        }
    }
}

void solve(set<int>s, int *P, int mx, int N, int W) {
    if(s.size()==1) {
        P[*s.begin()] = mx;
        return;
    }
    int B[N] = {0}, R[N] = {0};
    int val = W / s.size();
    val = min(val, lim[mx]);

    for(int j : s) {
        B[j] = val;
    }
    playRound(B, R);

    set<int>bigger;
    for(int j : s) {
        if(R[j]>B[j]) {
            bigger.insert(j);
        }
    }
    for(int x : bigger) {
        s.erase(x);
    }

    solve(bigger, P, mx, N, W);
    mx -= bigger.size();
    solve(s, P, mx, N, W);
}
bool cmp(int i, int j) {
    int B[100] = {0}, R[100] = {0};

    B[i] = B[j] = 100;
    playRound(B, R);

    if(R[i]>B[i]) return false;
    return true;
}

void m_sort(vector<int>&order, int l, int r) {
    if(l==r) return;

    int m = (r-l+1)/2;
    m_sort(order, l, l+m), m_sort(order, l+m+1, r);

    vector<int>t1, t2;
    for(int i=l; i<=l+m; ++i) t1.push_back(order[i]);
    for(int i=l+m+1; i<=r; ++i) t2.push_back(order[i]);

    reverse(t1.begin(), t1.end());
    reverse(t2.begin(), t2.end());

    int p = l;
    while(!t1.empty() || !t2.empty()) {
        if(t1.empty()) {
            order[p] = t2.back();
            t2.pop_back(); 
            ++p;
        } else if(t2.empty()) {
            order[p] = t1.back();
            t1.pop_back();
            ++p;
        } else {
            if(cmp(t1.back(), t2.back())) {
                order[p] = t1.back();
                t1.pop_back();
                ++p;
            } else {
                order[p] = t2.back();
                t2.pop_back();
                ++p;
            }
        }
    }
}
void allValues(int N, int W, int *P) {
    if (W == 2*N) {
        vector<int>order(N);
        iota(order.begin(), order.end(), 0);

        m_sort(order, 0, N-1);
        for(int i=0; i<N; ++i) {
            P[order[i]] = i+1;
        }
    } else {
        int S = 0;
        for(int i=1, cur=1; i<=N; ++i) {
            if(i>S) S += cur, ++cur;
            lim[i] = cur-2;
        }

        set<int>s;
        for(int i=0; i<N; ++i) {
            s.insert(i);
        }
        solve(s, P, N, N, W);
    }
}

Compilation message

koala.cpp: In function 'int minValue(int, int)':
koala.cpp:21:1: warning: control reaches end of non-void function [-Wreturn-type]
   21 | }
      | ^
koala.cpp: In function 'int greaterValue(int, int)':
koala.cpp:71:1: warning: control reaches end of non-void function [-Wreturn-type]
   71 | }
      | ^

Subtask #1
4.0 / 4.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 208 KB Output is correct
2 Correct 14 ms 328 KB Output is correct
3 Correct 13 ms 324 KB Output is correct
4 Correct 13 ms 208 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 344 KB Output is correct
2 Correct 46 ms 340 KB Output is correct
3 Correct 40 ms 336 KB Output is correct
4 Correct 40 ms 328 KB Output is correct
5 Correct 39 ms 324 KB Output is correct
6 Correct 40 ms 336 KB Output is correct
7 Correct 39 ms 336 KB Output is correct
8 Correct 43 ms 340 KB Output is correct
9 Correct 46 ms 336 KB Output is correct
10 Correct 45 ms 344 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 473 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 336 KB Output is correct
2 Correct 3 ms 336 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 3 ms 336 KB Output is correct
5 Correct 3 ms 336 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 3 ms 336 KB Output is correct
8 Correct 4 ms 336 KB Output is correct
9 Correct 3 ms 336 KB Output is correct
10 Correct 3 ms 336 KB Output is correct
11 Correct 3 ms 336 KB Output is correct
12 Correct 3 ms 336 KB Output is correct
13 Correct 3 ms 336 KB Output is correct
14 Correct 3 ms 336 KB Output is correct
15 Correct 3 ms 336 KB Output is correct
16 Correct 3 ms 340 KB Output is correct
17 Correct 3 ms 336 KB Output is correct
18 Correct 3 ms 336 KB Output is correct
19 Correct 3 ms 336 KB Output is correct
20 Correct 3 ms 336 KB Output is correct
21 Correct 3 ms 336 KB Output is correct
22 Correct 3 ms 336 KB Output is correct
23 Correct 3 ms 336 KB Output is correct
24 Correct 3 ms 336 KB Output is correct
25 Correct 4 ms 336 KB Output is correct
26 Correct 3 ms 336 KB Output is correct
27 Correct 3 ms 344 KB Output is correct
28 Correct 3 ms 336 KB Output is correct
29 Correct 3 ms 336 KB Output is correct
30 Correct 3 ms 336 KB Output is correct
31 Correct 3 ms 336 KB Output is correct
32 Correct 4 ms 336 KB Output is correct
33 Correct 3 ms 336 KB Output is correct
34 Correct 3 ms 336 KB Output is correct
35 Correct 3 ms 336 KB Output is correct
36 Correct 3 ms 336 KB Output is correct
37 Correct 3 ms 344 KB Output is correct
38 Correct 3 ms 336 KB Output is correct
39 Correct 3 ms 336 KB Output is correct
40 Correct 3 ms 336 KB Output is correct