oj.uz

Submission #701292

# Submission time Handle Problem Language Result Execution time Memory
701292 2023-02-20T18:56:21 Z Abrar_Al_Samit Koala Game (APIO17_koala) C++17
86 / 100
 53 ms 344 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+1)/2;

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

        if(B[0]<R[0] && B[1]<R[1]) {
            l = mid;
        } 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];

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

    if(R[i]>B[i]) return false;
    return true;
}
void allValues(int N, int W, int *P) {
    if (W == 2*N) {
        vector<int>order(N);
        iota(order.begin(), order.end(), 0);

        sort(order.begin(), order.end(), cmp);
        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 4 ms 208 KB Output is correct
2 Correct 4 ms 208 KB Output is correct
3 Correct 5 ms 320 KB Output is correct
4 Correct 4 ms 208 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
14.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 332 KB Output is correct
2 Partially correct 48 ms 208 KB Output is partially correct
3 Correct 39 ms 324 KB Output is correct
4 Correct 53 ms 344 KB Output is correct
5 Partially correct 40 ms 336 KB Output is partially correct
6 Correct 43 ms 316 KB Output is correct
7 Partially correct 42 ms 328 KB Output is partially correct
8 Correct 40 ms 332 KB Output is correct
9 Correct 45 ms 332 KB Output is correct
10 Correct 39 ms 336 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 208 KB Output is correct
2 Incorrect 37 ms 208 KB Output isn't correct
3 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 336 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 336 KB Output is correct
7 Correct 3 ms 336 KB Output is correct
8 Correct 3 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 344 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 4 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 5 ms 336 KB Output is correct
26 Correct 4 ms 336 KB Output is correct
27 Correct 3 ms 336 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 3 ms 344 KB Output is correct
33 Correct 4 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 4 ms 336 KB Output is correct
37 Correct 3 ms 336 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