oj.uz

Submission #1104107

# Submission time Handle Problem Language Result Execution time Memory
1104107 2024-10-22T20:02:14 Z makrav Koala Game (APIO17_koala) C++14
100 / 100
 46 ms 644 KB 
#include "koala.h"
#include <bits/stdc++.h>

using namespace std;

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

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

int maxValue(int N, int W) {
    int B[100], R[100];
    for (int i = 0; i < N; i++) {
        B[i] = 1;
    }
    playRound(B, R);
    vector<int> ps;
    for (int i = 0; i < N; i++) {
        if (R[i] == 2) ps.push_back(i);
    }
    for (int i = 0; i < N; i++) B[i] = 0;
    for (int i = 0; i < 50; i++) B[ps[i]] = 2;
    playRound(B, R);
    ps.clear();
    for (int i = 0; i < N; i++) {
        if (R[i] == 3) ps.push_back(i);
    }
    for (int i = 0; i < N; i++) B[i] = 0;
    for (int i = 0; i < 25; i++) B[ps[i]] = 4;
    playRound(B, R);
    ps.clear();
    for (int i = 0; i < N; i++) {
        if (R[i] == 5) ps.push_back(i);
    }
    for (int i = 0; i < N; i++) B[i] = 0;
    for (int i = 0; i < ps.size(); i++) B[ps[i]] = 11;
    playRound(B, R);
    for (int i = 0; i < N; i++) {
        if (R[i] == 12) return i;
    }
    return 0;
}

mt19937 rnd(time(NULL));

int greaterValue(int N, int W) {
    int B[100], R[100];
    for (int i = 0; i < 100; i++) B[i] = 0;
    int L = 1, RG = 9;
    while (L <= RG) {
        int M = (L + RG) / 2;
        B[0] = B[1] = M;
        playRound(B, R);
        if (R[0] > B[0] && R[1] > B[1]) L = M + 1;
        else if (R[0] <= B[0] && R[1] <= B[1]) RG = M -1;
        else {
            return (R[0] < R[1]);
        }
    }
    B[0] = B[1] = L;
    playRound(B, R);
    return R[0] < R[1];
}

struct xd {
    pair<int, int> vals_seg;
    vector<int> poss;
};

void allValues(int N, int W, int *P) {
    int B[100], R[100];
        vector<xd> lol;
        vector<int> ap(N);
        iota(all(ap), 0);
        lol.pb({{1, N}, ap});
        while (lol.size() < N) {
            //cout << "yep" << endl;
            vector<xd> new_lol;
            for (int i = 0; i < sz(lol); i++) {
                if (lol[i].poss.size() == 1) {
                    new_lol.pb(lol[i]);
                    continue;
                }
                int l = lol[i].vals_seg.first, r = lol[i].vals_seg.second;
                int sm = 0;
                for (int j = l; j <= r; j++) sm += j;
                bool good = false;
                pair<int, int> cs;
                for (int cost = 1; cost * (r - l + 1) <= W; cost++) {
                    if (good) break;
                    for (int c2 = 0; c2 * (l - 1) + cost * (r - l + 1) <= W && (l != 1 || c2 <= 0); c2++) {
                        if (good) break;
                        int cntif0 = min(l - 1, (W - (N - r)) / (c2 + 1));
                        int cntifall = min(l - 1, max(0, ((W - (N - r)) - (cost + 1) * (r - l + 1)) / (c2 + 1)));
                        int currans = max((2 * l - 1 - cntif0) * cntif0 / 2, sm + (2 * l - 1 - cntifall) * cntifall / 2);
                        if ((r - l + 1) * (cost + 1) + N - r > W) {
                            currans = (2 * l - 1 - cntif0) * cntif0 / 2;
                        }
                        for (int newcnt = 1; newcnt < r - l + 1; newcnt++) {
                            int curcnt = min(l - 1, max(0, ((W - (N - r)) - newcnt * (cost + 1)) / (c2 + 1)));
                            if (currans < (2 * r - newcnt + 1) * newcnt / 2 + (2 * l - 1 - curcnt) * curcnt / 2) {
                                cs = {cost, c2};
                                good = true;
                                break;
                            }
                        }   
                    }
                }

                for (int j = 0; j < 100; j++) {
                    B[j] = 0;
                }
                for (int j = 0; j < i; j++) {
                    for (int pos : lol[j].poss) B[pos] = cs.second;
                }
                for (int pos : lol[i].poss) B[pos] = cs.first;
                playRound(B, R);

                vector<int> highs, lows;
                for (int pos : lol[i].poss) {
                    if (R[pos] > B[pos]) highs.pb(pos);
                    else lows.pb(pos);
                }
                new_lol.pb({{lol[i].vals_seg.first, lol[i].vals_seg.first + lows.size() - 1}, lows});
                new_lol.pb({{lol[i].vals_seg.first + lows.size(), lol[i].vals_seg.second}, highs});
            }   
            swap(new_lol, lol);
        }

        for (int i = 0; i < N; i++) {
            P[lol[i].poss[0]] = i + 1;
        }
}

Compilation message

koala.cpp: In function 'int maxValue(int, int)':
koala.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i = 0; i < ps.size(); i++) B[ps[i]] = 11;
      |                     ~~^~~~~~~~~~~
koala.cpp: In function 'void allValues(int, int, int*)':
koala.cpp:86:27: warning: comparison of integer expressions of different signedness: 'std::vector<xd>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   86 |         while (lol.size() < N) {
      |                ~~~~~~~~~~~^~~

Subtask #1
4.0 / 4.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 4 ms 336 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
18.0 / 18.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 336 KB Output is correct
2 Correct 5 ms 336 KB Output is correct
3 Correct 5 ms 588 KB Output is correct
4 Correct 6 ms 336 KB Output is correct
5 Correct 5 ms 336 KB Output is correct
6 Correct 6 ms 336 KB Output is correct
7 Correct 6 ms 460 KB Output is correct
8 Correct 6 ms 336 KB Output is correct
9 Correct 6 ms 336 KB Output is correct
10 Correct 5 ms 352 KB Output is correct
11 Correct 5 ms 336 KB Output is correct
12 Correct 5 ms 336 KB Output is correct
13 Correct 5 ms 504 KB Output is correct
14 Correct 5 ms 336 KB Output is correct
15 Correct 5 ms 336 KB Output is correct
16 Correct 5 ms 336 KB Output is correct
17 Correct 6 ms 336 KB Output is correct
18 Correct 5 ms 336 KB Output is correct
19 Correct 5 ms 336 KB Output is correct
20 Correct 6 ms 508 KB Output is correct

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 484 KB Output is correct
8 Correct 3 ms 336 KB Output is correct
9 Correct 3 ms 336 KB Output is correct
10 Correct 4 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 472 KB Output is correct
14 Correct 3 ms 504 KB Output is correct
15 Correct 3 ms 336 KB Output is correct
16 Correct 3 ms 336 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 504 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 472 KB Output is correct
24 Correct 4 ms 336 KB Output is correct
25 Correct 3 ms 336 KB Output is correct
26 Correct 3 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 476 KB Output is correct
32 Correct 3 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 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